3Sum - LeetCode

Brutal Force?

가장 처음에 떠오르는 생각은 완전탐색 브루탈 포스를 활용하는 것이다. 하지만 3개의 수의 합을 구하는 문제에서 완전탐색을 사용하면 O(N^3)이다. 너무 오래 걸릴 것이다. 실제로 채점을 해보면 타임 아웃이 된다. (코드는 생략)

Dictionary를 활용한 풀이

문제 풀이 아이디어

최소한 O(N^2)의 풀이를 사용해야 할 것 같다. 반복문을 한 단계 줄이면 되는 것이다. 반복문을 줄이는 방법으로 가장 간단한 방법은 Dictionary나 Set을 활용하는 것이다. 여기서는 Dictionary를 사용해서 시간을 줄여보았다. 먼저 nums 배열에 있는 값들을 [value: index]의 형태로 dictionary로 저장한다. 그리고 이중 반복문으로 2개의 수를 뽑은 다음에 두 수의 합쳐서 0이 되는 값이 dictionary에 있는지 찾는다. dictionary에서 key를 통해 value를 구하는 것은 O(1)이다. 따라서 O(N^2)의 시간복잡도로 구현할 수 있다. (나머지 디테일은 코드 참고)

코드

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        // 중복을 거르기 위해서 Set에 저장
        var ans = Set<[Int]>()
        
        // dict에 값을 key로 index를 value로 저장
        var dict = [Int:Int]()
        for (i, v) in nums.enumerated() {
            dict[v] = i
        }
        
        // 이중반복문으로 일단 숫자 2개를 매칭
        for i in 0..<(nums.count - 1) {
            for j in (i + 1)..<nums.count {
                // 두 수와 더해서 0이 될 수 있는 값(=target)이 dict에 있는지 확인한다.
                // i, j, k는 서로 달라야 하므로 k > j인지 확인한다.
                let target = 0 - nums[i] - nums[j]
                if let k = dict[target], k > j {
                    // 중복 확인을 위해서 정렬한다.
                    ans.insert([nums[i], nums[j], nums[k]].sorted())
                }
            }
        }
        
        // Array로 변환해서 리턴한다.
        return Array(ans)
    }
}

투포인터

문제 풀이 아이디어

위 코드를 채점해보면 대략 상위 60% 정도로 그렇게 빠른 실행속도를 보이지는 않는다. 일단 매번 정렬을 해주어야 하고 Set → Array로 변환하는데에 드는 시간도 있기 때문이다. 따라서 좀 더 빠른 실행을 위해 투포인터를 사용해보겠다.

위 문제는 3개의 수를 합치지만 어떻게 “투” 포인터를 활용해서 풀 수 있을까? i, j, k중에 첫 번째 i는 고정을 시켜놓고 나머지 j, k를 투 포인터로 이동해가면서 합이 0이 되는 값을 찾으면 된다.

투 포인터를 사용하기 위해서는 일단 주어진 숫자들이 정렬되어 있어야 한다. 그래야지 합이 크거나 작을 때 포인터를 상황에 맞추어 이동할 수 있기 때문이다.

주의할 점은 중복된 값이 없어야 한다는 점이다. 따라서 일단 투포인터를 통해서 0이 되는 값을 구했다면 중복된 값 (즉 j는 다르지만 nums[j]는 동일한 값)은 스킵해주어야 한다.

이렇게 문제를 풀면 일단 중복된 값이 ans 배열에 들어갈 일이 없으므로 Set → Array의 형변환에 드는 비용을 줄일 수 있다. 또한 매번 정렬하지 않고 한번만 정렬하므로 그 비용 역시 줄일 수 있다.

코드

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        // 투포인터를 활용하기 위한 정렬
        let nums = nums.sorted()
        var ans = [[Int]]()

        for i in 0 ..< nums.count {
            // 동일한 숫자 조합이 포함되면 안되니까 중복된 nums[i]가 없도록
            if i > 0 && nums[i - 1] == nums[i] { continue }
            var left = i + 1
            var right = nums.count - 1
            while left < right {
                let sum = nums[i] + nums[left] + nums[right]
                // 합이 0일 때
                if sum == 0 {
                    // ans에 추가
                    ans.append([nums[i], nums[left], nums[right]])
                    // 동일한 숫자 조합이 포함되면 안되니까 중복된 nums[left]가 없도록
                        // nums[left]만 달라지면 right는 당연히 중복되지 않으므로 right는 이동할 필요 없다
                    while left < right, nums[left + 1] == nums[left] {
                        left += 1
                    }
                    left += 1
                // 합이 0보다 작으면 합이 커지도록 left + 1
                } else if sum < 0 {
                    left += 1
                // 합이 0보다 트면 합이 작아지도록 right - 1
                } else {
                    right -= 1
                }
            }
        }
        return ans
    }
}