[leetCode] 13. 3Sum (알고리즘, 원리) with Swift

leetCode submit 통과하면 다른 분들이 짜 놓으신 환상적인 알고리즘 볼 수 있습니다. 제껀 참고와 통과용으로 봐주세요 ㅠㅠ

효율성 갖다버린 코드입니다. 허헣

 

다른 글에서 얼핏 노가다 코드라고 적힌 걸 봤어요 ㅎㅎ 아마 다른 방법으로 탐색하는 것도 있겠지만 어떻게든 탐색 범위를 줄이는 것이 이 문제에서 time 복잡도를 줄일 수 있는 방법이 아닐까 싶습니다. 

 

👇광고 붙이고 문제랑 예시 올리면 안된다고 들어서 문제는 링크로 대신합니다 👇

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

3Sum - LeetCode

알고리즘

우선 정렬을 해주어야 합니다! 정렬을 해주는 이유는 두 가지 정도 인데요, 첫 번째로는 중복되는 숫자를 바로 옆 인덱스와 비교해서 알 수 있고, 두번째는 세개의 숫자를 더한 값에서 유연하게 대처하기 위해서 입니다.

세개의 숫자를 더한 값이 만약 0보다 크다면 현재 세개의 숫자 합에서 어떤 숫자를 작게 만들어 주면 되는 것이고, 만약 세개의 숫자를 더한 값이 0보다 작다면 세개의 숫자 합에서 어떤 숫자를 그 보다 더 큰 것으로 대처해 주면 되는 것입니다. 

👇자세한 설명은 아래 유튜브를 통해 참고했습니다👇

https://www.youtube.com/watch?v=6qgC-dqKElA

우선 주어진 nums 어레이를 sort 해줍니다. 스위프트로는 

nums.sort()

해주시면 배열을 정렬할 수 있습니다. 

현재 값 current를 첫 번째 인덱스 인 -4로 지정하고 첫번째 인덱스 바로 옆에 인덱스를 leftIndex, 맨 마지막 인덱스를 rightIndex로 지정해줍니다. 이때 세개의 값을 더합니다.  total sum = current + left + right 각 인덱스에 있는 값을 더해주고 0과 비교합니다. 

위 그림에서 세개의 숫자 합은 -3이므로 0보다 작기 때문에 큰 숫자가 필요하게 됩니다.

이때 빨간 선을 봐주세요! 세개의 숫자 중 하나를 큰 숫자로 바꿔 준다면 0 과 가까워 지게 되는 원리 입니다. 따라서 + 방향으로 left를 이동해 주면 값이 점점 커지므로 현재 left에 있는 숫자보다 더 큰 값으로 값을 바꿀 수 있습니다. (현재는 -1 옆에 -1이지만...)

계속 옮겨 주다가 만약 세개의 합이 0보다 크게 되면 right. 인덱스를 - 방향으로 옮겨서 총 합의 크기를 작게 해주시면 됩니다.

이렇게 하다가 원하는 배열 조합을 찾지 못하면 current 인덱스를 옮겨 줍니다,

left 인덱스는 무조건 current  인덱스의 +1 에서 시작해야 하고 right는 마지막 인덱스로 지정해 주면 되는데 

이는 current index의 왼쪽을 신경 써주지 않아도 되기 때문입니다. 이미 탐색을 했기 때문입니다. 

 

이를 그대로 해주면 세상에 하위 7%가 나옵니다!

앞서 적었듯이 탐색 범위를 줄여 주셔야 해요 ㅎㅎㅎㅎ

그 중 하나는 복수의 값에 대처 하는 것입니다.

문제에서 제시했던 복수 조합도 줄여줄 뿐만 아니라 이렇게 해주어야 탐색 범위와 시간도 줄어 듭니다. 

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        
        var newNums = nums
        newNums.sort()
        var answer = [[Int]]()
        
        var currentIndex = 0
        var leftIndex = currentIndex + 1
        var lastIndex = newNums.count - 1
        var rightIndex = lastIndex
        
        while currentIndex < newNums.count - 2 {
            if  (currentIndex != 0) && (newNums[currentIndex] == newNums[currentIndex-1]) {
                currentIndex += 1
                leftIndex = currentIndex + 1
                rightIndex = lastIndex
                continue
            }
            while leftIndex != rightIndex {
                
                let currentSum = newNums[currentIndex] + newNums[leftIndex] + newNums[rightIndex]
                
                if currentSum < 0 {
                    leftIndex += 1
                }
                
                if currentSum > 0 {
                    rightIndex -= 1
                }
                
                if currentSum == 0 {
                    let subAnswerArray = [newNums[currentIndex], newNums[leftIndex], newNums[rightIndex]]
                    answer.append(subAnswerArray)
                    leftIndex += 1
                }
            }
            
            currentIndex += 1
            leftIndex = currentIndex + 1
            rightIndex = lastIndex
        }
        return Array(Set(answer))
    }
}

우선 통과한 코드인데 추후에 효율성 고려해서 마지막 복수 제거하려고 넣은 set 부분을 고쳐봐야 될거 같아요 ㅠㅠ

 

첫 반복문의 범위는 

우선 현재 인덱스에서 오른쪽에 있는 두개의 숫자로 조합하므로 마지막 인덱스를 count-1이라 할 때 오른쪽에 두 개의 숫자를 남겨야 하므로 count-3 까지만 반복하여 조회하면 됩니다. 따라서 범위는 0 < index < count-2 가 됩니다.