swift leetcode Two Sum 풀기

문제

Int형 배열이 주어졌을때 두개의 원소를 더해서 target을 만들수 있는 Index를 반환하는 문제입니다. 예를들어 nums = [2,7,11,15], target = 9일때 결과 값은 [0, 1]인 것입니다. 결과값은 오직 하나라고 하고, 같은 위치에 있는 원소를 두번 더하는 것은 안된다고 합니다. 조건은 nums의 길이는 2 부터 10000까지 입니다 O(N^2)로 풀었을때 1억의 연산량이라고 생각하면 되니 얼추 N^2까지 가능 해보입니다.

풀이

먼저 제일 쉽게 떠오르는 방법은 완전 탐색 입니다. [1,2,3,4,5] 가 있다고 한다면 1부터 시작해서 (1,2) (1,3) (1,4) (1,5) ... (4,5)까지 하나씩 비교 하는 방법 입니다.

0부터 n까지 그리고 i+1 부터 n까지 이중 루프로 모두 검색해서 찾아내는 방법입니다.

// O(N^2)
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for i in 0..<nums.count {
            for j in i+1..<nums.count {
                if nums[i] + nums[j] == target {
                    return [i, j]
                }
            }
        }
        return []
    }
}

 

두번째 방법으로는 해시테이블을 사용하는 방법입니다. 시간복잡도는 O(N)입니다. 한번 탐색한 원소는 Dictionary에 그 값과 위치를 저장하고 원소를 탐색할때 내가 필요한 원소를 Dict에 존재하나 찾아보는 방식입니다.

// O(n)
class Solution2 {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var table: [Int:Int] = [:]
        for i in 0..<nums.count {
            if let index = table[target - nums[i]] {
                return [index, i]
            }
            table[nums[i]] = i
        }
        return []
    }
}

앞으로 매일 한 문제씩 leetcode를 통해 코딩테스트를 준비하려 합니다. 그럼 안녕~!