[LeetCode] 15. 3Sum

문제

leetcode.com/problems/3sum/

3Sum - LeetCode

 

코드

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var arraySet = Set<[Int]>()
        var sortedNums = nums.sorted()
        var maxIndex = sortedNums.count-1
        for y in 0..<sortedNums.count {
            if y > 0, sortedNums[y] == sortedNums[y-1] {
                continue
            }

            var left = y+1
            var right = maxIndex

            while(left < right) {
                var sum = sortedNums[y] + sortedNums[left] + sortedNums[right]
                if sum > 0 {
                    right -= 1
                } else if sum < 0 {
                    left += 1
                }else {
                    arraySet.insert([sortedNums[y], sortedNums[left], sortedNums[right]])
                    while left < maxIndex, sortedNums[left] == sortedNums[left+1] {
                        left += 1
                    }
                    while 0 < right, sortedNums[right] == sortedNums[right-1] {
                        right -= 1
                    }
                    left += 1
                    right -= 1
                }
            }        
        }
        return Array(arraySet)
    }
}

 

설명

투포인터 알고리즘을 사용해야 합니다. 

해당 문제에선, 왼쪽과 오른쪽에 포인터를 두고, 값의 합이 적당한지 비교해가며 포인터를 옮기는 방식으로 구현했습니다.

또한, 투포인터 알고리즘 전, 배열을 정렬하였지요.

로직을 그림?으로 표현하면 다음과 같습니다.

그림?으로 표현하다 보니, 추가 종료시점이 보여서, 더욱 최적화 할수 있겠네요

여러분들은 추가 종료 시점이 보였나요? (불필요 계산 부분)

 

1. sortedNums[y] > 0 인 경우

sortedNums을 정렬했으니, y번째의 값이 0을 넘었다면 y+1, y+2, ... 번째 값 모두 0이상의 값이겠네요?

양수 3개를 아무리 더해도 0이 불가능 하니, 종료 시점이 되겠죠.

 

2. y == sortedNums.count-2 인 경우

제가 구현한 로직에선 y < L < R 이죠

y == sortedNums.count-2인 경우, L은 sortedNums.count-1을 갖겠죠? 그럼 R은 sortedNums.count을 가져야겠네요.

Right의 값이 배열 범위를 초과하여 종료해도 되겠어요.

 

여러분들이 최적화 해보세요. 쉽죠?

 

회고

사실 투포인터 알고리즘 개념은 알고있었지만, 이렇게 사용할 줄은 몰랐네요. 충격이에요.

값들의 정보를 알아야하기 때문에, 이중 배열을 활용하여 빅오 n의 3승으로 종료 타이밍을 보다가, 풀지 못했습니다.

하지만, 이런 고민과 시도는 나쁘지 않았다고 생각합니다. 고민을 해야, 머릿속에 남죠.

이렇게 하나 더 배워 갑니다.

아래는 문제를 풀기위해 끄적인 내용들이에요