[leetcode] 3sum (swift)

문제 

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

3Sum - LeetCode

문제요약

a + b + c = 0 이 되는 숫자조합을 고르는 문제입니다. 주어지는 배열의 범위는 3 <= nums.length <= 3000 입니다.

풀이

숫자배열의 길이의 최대가 3000개이므로 O(N^2)의 시간복잡도까지 허용되는 문제라는 것을 예측할 수 있습니다. O(N^3) 또는 O(N^2logN)의 시간복잡도 풀이가 3개의 숫자를 골라 합을 구하는 문제로 일반적이지만 시간초과 풀이입니다. 

 

a + b + c = 0이 되는 경우를 구하기 위해서 3개의 숫자 a, b, c를 구해야 합니다. 먼저 숫자하나를 구하기 위해선 N만큼 순회할 수 있습니다. 나머지 숫자들 b, c를 구하기 위해서는 정렬된 배열 속에서 쉽게 구할 수 있습니다. 숫자가 -3, -2, -1, 0, 1, 2, 3과 같이 정렬이 되어 있고, -3을 a라고 가정합니다. b와 c를 구하기 위해서 남은 배열중 왼쪽과 오른쪽에서부터 중앙으로 좁혀오는 풀이가 있습니다. 만일 3개의 숫자의 합이 0보다 크다면 right를 1 감소시키고 0보다 작다면 left를 1 증가시킵니다. 그렇게 left < right가 될 때까지 0이 나오는 모든 경우의 수를 구합니다. 

 

추가로, 중복을 제거해야 합니다. 중복을 제거하는 방법엔 2가지가 있습니다. 

 

1. Set로 선언하기 

2. 같은 수일 경우, 건너뛰기

 

2번을 자세히 설명하자면, 만약 a를 선택하는 과정에서 같은 숫자일 경우 똑같은 경우의 수가 나오므로 생략할 수 있습니다. 또한 left와 right를 고르는 과정 속에서 이전 left와 이전 right가 현재 left와 right와 같을 경우 1을 한번더 증감시킬 수 있습니다. 2번 방법을 선택하면 시간을 더 감소시킬 수 있습니다. 

풀이코드1

Runtime 111ms | Memory 182.MB