Two Sum - LeetCode

문제 풀이 아이디어

브루탈 포스?

브루탈 포스 (완전 탐색)은 이 문제를 가장 쉽게 푸는 방법이다. 그냥 이중반복문으로 두 수를 더해가면서 target이 나오면 리턴하면 된다. 하지만 시간복잡도가 O(n^2)가 된다. 더 빠른 방법은 없을까?

dictionary 활용하기

dictionary를 사용하면 더 빠르게 풀 수 있다. 포인트는 key에 index를 할당하는 것이 아니라 값을 할당하는 것이다. 즉 [index:value]의 dictionary를 사용한다. 주어진 배열을 순회하면서 target - (현재 값)이 존재하는 경우 dictionary에 저장된 index를 현재 index와 함께 반환하면 된다. 존재하지 않는 경우에는 dictionary에 현재 값과 index를 저장하고 넘어간다. dictionary에서 특정 값을 조회하는 것은 O(1)이다. 따라서 시간복잡도는 주어진 배열을 1회 순회하는 것과 동일한 O(n)이다.

주의할 점은 dictionary에 target - (현재 값)을 찾기 전보다 먼저 현재 값과 현재 index를 저장하면 안된다는 것이다. 만약 target이 현재 값의 1/2이라면 같은 Index 2를 리턴할 가능성이 있기 때문이다. 예를 들어 6이고 값이 3이라면 [(현재 index), (현재 index)]를 리턴할 수 있다.

코드

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        // [num:index]를 저장하는 dictionary
        var dict = [Int:Int]()
        
        for (i, v) in nums.enumerated() {
            // 현재 v와 더해서 target을 만들 수 있는 수가 등장하면?
            if let index = dict[target - v] {
                return [index, i] // index 2개를 리턴 (index가 i보다 항상 작으므로 이 순서로 리턴)
            }
            // 없으면 dictionary에 기록
            dict[v] = i
        }
        return []
    }
}