가장 처음에 떠오르는 생각은 완전탐색 브루탈 포스를 활용하는 것이다. 하지만 3개의 수의 합을 구하는 문제에서 완전탐색을 사용하면 O(N^3)이다. 너무 오래 걸릴 것이다. 실제로 채점을 해보면 타임 아웃이 된다. (코드는 생략)
최소한 O(N^2)의 풀이를 사용해야 할 것 같다. 반복문을 한 단계 줄이면 되는 것이다. 반복문을 줄이는 방법으로 가장 간단한 방법은 Dictionary나 Set을 활용하는 것이다. 여기서는 Dictionary를 사용해서 시간을 줄여보았다. 먼저 nums 배열에 있는 값들을 [value: index]의 형태로 dictionary로 저장한다. 그리고 이중 반복문으로 2개의 수를 뽑은 다음에 두 수의 합쳐서 0이 되는 값이 dictionary에 있는지 찾는다. dictionary에서 key를 통해 value를 구하는 것은 O(1)이다. 따라서 O(N^2)의 시간복잡도로 구현할 수 있다. (나머지 디테일은 코드 참고)
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
// 중복을 거르기 위해서 Set에 저장
var ans = Set<[Int]>()
// dict에 값을 key로 index를 value로 저장
var dict = [Int:Int]()
for (i, v) in nums.enumerated() {
dict[v] = i
}
// 이중반복문으로 일단 숫자 2개를 매칭
for i in 0..<(nums.count - 1) {
for j in (i + 1)..<nums.count {
// 두 수와 더해서 0이 될 수 있는 값(=target)이 dict에 있는지 확인한다.
// i, j, k는 서로 달라야 하므로 k > j인지 확인한다.
let target = 0 - nums[i] - nums[j]
if let k = dict[target], k > j {
// 중복 확인을 위해서 정렬한다.
ans.insert([nums[i], nums[j], nums[k]].sorted())
}
}
}
// Array로 변환해서 리턴한다.
return Array(ans)
}
}
위 코드를 채점해보면 대략 상위 60% 정도로 그렇게 빠른 실행속도를 보이지는 않는다. 일단 매번 정렬을 해주어야 하고 Set → Array로 변환하는데에 드는 시간도 있기 때문이다. 따라서 좀 더 빠른 실행을 위해 투포인터를 사용해보겠다.
위 문제는 3개의 수를 합치지만 어떻게 “투” 포인터를 활용해서 풀 수 있을까? i, j, k중에 첫 번째 i는 고정을 시켜놓고 나머지 j, k를 투 포인터로 이동해가면서 합이 0이 되는 값을 찾으면 된다.
투 포인터를 사용하기 위해서는 일단 주어진 숫자들이 정렬되어 있어야 한다. 그래야지 합이 크거나 작을 때 포인터를 상황에 맞추어 이동할 수 있기 때문이다.
주의할 점은 중복된 값이 없어야 한다는 점이다. 따라서 일단 투포인터를 통해서 0이 되는 값을 구했다면 중복된 값 (즉 j는 다르지만 nums[j]는 동일한 값)은 스킵해주어야 한다.
이렇게 문제를 풀면 일단 중복된 값이 ans 배열에 들어갈 일이 없으므로 Set → Array의 형변환에 드는 비용을 줄일 수 있다. 또한 매번 정렬하지 않고 한번만 정렬하므로 그 비용 역시 줄일 수 있다.
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
// 투포인터를 활용하기 위한 정렬
let nums = nums.sorted()
var ans = [[Int]]()
for i in 0 ..< nums.count {
// 동일한 숫자 조합이 포함되면 안되니까 중복된 nums[i]가 없도록
if i > 0 && nums[i - 1] == nums[i] { continue }
var left = i + 1
var right = nums.count - 1
while left < right {
let sum = nums[i] + nums[left] + nums[right]
// 합이 0일 때
if sum == 0 {
// ans에 추가
ans.append([nums[i], nums[left], nums[right]])
// 동일한 숫자 조합이 포함되면 안되니까 중복된 nums[left]가 없도록
// nums[left]만 달라지면 right는 당연히 중복되지 않으므로 right는 이동할 필요 없다
while left < right, nums[left + 1] == nums[left] {
left += 1
}
left += 1
// 합이 0보다 작으면 합이 커지도록 left + 1
} else if sum < 0 {
left += 1
// 합이 0보다 트면 합이 작아지도록 right - 1
} else {
right -= 1
}
}
}
return ans
}
}