LeetCode - 15. 3Sum - swift

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

숫자가 들어있는 배열( arr ) 이 주어지는데, 

이 배열에서,  arr[ i ]  + arr[ j ] + arr[ k ] == 0 이면서, 

i != j 이면서

j != k 이면서

i != k 인 경우의  [ arr[i] , arr[j], arr[k] ] 들을 찾는 문제다.

 

2개 이상의 경우에는 나름의 최적화가 필요하다. 

arr의 개수는 최대 3천 개다.

만약 이를 모든 경우의 수 3000 C 3 조합으로 찾는다면, 약 44억 번이 필요하다. 이는 시간 초과다.

 

우선 주어진 arr를 정렬시킨다. 

그리고 이제 arr을 모두 하나씩 탐색하는데, 

하나씩 탐색하는 것이 i 가 되고,

나머지 j, k 는 투 포인터로 찾아낸다. 

이미 배열의 값들이 정렬되어있으므로,  i, j, k들의 합이 0보다 큰지, 작은지, 같은지만 판별하여

j, k 들을 움직이면 된다. 

이렇게 O(N^2) 으로만 찾을 수 있게 된다. 

 

아래와 같이 첫 번째 풀이로, 풀어도 시간이 쪼금 걸리지만 풀리긴 한다. 

오래 걸리는 이유는, 답을 return 할 때는 중복된 값이 있으면 안 된다.

그래서 대신에 set을 이용했는데, 그 과정에서 매번 값들을 정렬시켜 insert하는 오버헤드가 존재하기 때문이다.

 

다른 분의 코드를 참고하여, Set을 이용하지 않고도 푸는 방법을 알게 됐다.

전반적인 코드는 동일하지만, 중복을 미리 거르는 방법이다.

i와 j가 같은 경우를 미리 판별하는 방법이다. 

그럼 굉장히 빠르게 O(N^2)의 시간으로 풀리게된다. 

 

 

첫 번째 풀이  ( 오버헤드 존재 ) 

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        let nums = nums.sorted(by: <)
        var ans = Set<[Int]>()
        for i in 0..<nums.count {
            var l = i+1
            var r = nums.count-1
            if l >= r { break }
            while l<r {
                let tempt = (nums[i] + nums[l] + nums[r])
                if tempt > 0 {
                    r -= 1
                } else if tempt < 0 {
                    l += 1
                } else {
                    let list = [nums[i], nums[l], nums[r]].sorted(by: <)
                    ans.insert(list)
                    l += 1
                    r -= 1
                }
            }
        }
        return Array(ans)
    }
}

 

 

두 번째 풀이  ( 오버헤드 제거 ) 

 

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        let nums = nums.sorted(by: <)
        var ans = [[Int]]()
        for i in 0..<nums.count {
            if i > 0, nums[i] == nums[i-1] { continue }
            var l = i+1
            var r = nums.count-1
            if l >= r { break }
            while l<r {
                let tempt = (nums[i] + nums[l] + nums[r])
                if tempt > 0 {
                    r -= 1
                } else if tempt < 0 {
                    l += 1
                } else {
                    let list = [nums[i], nums[l], nums[r]]
                    ans.append(list)
                    l += 1
                    r -= 1
                    while l < r, nums[l] == nums[l-1], nums[r] == nums[r+1] {
                        l += 1
                        r -= 1
                    }
                }
            }
        }
        return ans
    }
}