[Leetcode/Medium] 세 수의 합 (15. 3Sum, Swift)

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

 

🤔 문제 설명

배열 nums를 입력받아 합으로 0을 만들 수 있는 3개의 요소를 출력하세요.

단, 결과 배열에는 동일한 요소가 들어가지 않으며, 중복된 삼중항이 포함되어서는 안 됩니다. 

nums = [-1,0,1,2,-1,-4]
// [[-1,-1,2],[-1,0,1]]

 

💡 풀이

일단 바로 생각나는 것은 반복문 3개를 중첩해서 사용하는 방법이었다.

물론 그렇게 해도 올바른 답은 나오겠지만, 그 뻔한 방법 말고 지난번 풀이에서 사용했던 투 포인터 방법을 사용해볼려고 했다.

순차적으로 들어온 nums 배열을 반복하면서 값을 하나 빼두고(i) 나머지 뒤의 값을 대상으로 앞 뒤에 포인터를 두어서
sum값에 따라 음수라면 왼쪽에 있는 포인터를 +1, 양수라면 오른쪽에 있는 포인터를 -1, 0이라면 그 값을 결과 배열에 append 시켜주면 된다. 

이때 중복된 값이 배열에 추가되는 것을 막기 위해 Array가 아니라 Set으로 선언했고,
투 포인터의 작동을 위해 배열을 정렬한 뒤 (sortedNums = nums.sorted()) 반복했다는 것이 문제 해결의 특징이다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 735ms (Beats 15.23%), Memory : 20.90MB (Beats 15.48%)

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var result = Set<[Int]>()
        let sortNums = nums.sorted()

        for i in 0..<sortNums.count {
            var left = i+1
            var right = nums.count-1

            while (left < right) {
                let candidate = [sortNums[i], sortNums[left], sortNums[right]]
                let sumCandidate = sortNums[i] + sortNums[left] + sortNums[right]
                
                if (sumCandidate < 0) { left += 1 } 
                else if (sumCandidate > 0) { right -= 1 } 
                else { 
                    result.insert(candidate)
                    left += 1
                    right -= 1
                }
            }
        }
        return Array(result)
    }
}