-
[LeetCode] 15. 3Sum / Swift프로그래밍/코딩테스트 2021. 7. 2. 01:54
[문제 보기]
더보기Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [] Output: []
Example 3:
Input: nums = [0] Output: []
Constraints:
- 0 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
https://leetcode.com/problems/3sum/
분명 2sum 문제는 풀었던 기억이 있었는데 2sum문제에서 푼 방법(brute force)는 역시 3이 되니 시간초과가 났다!
이번 문제도 역시 투포인터 문제였다.
k - 1까지는 한개씩 후보를 줄여나가면서 직접 찾고, 나머지 2개를 찾을 때는 투포인터를 사용한다.
여기서 중복되지 않는 부분을 잘 끼워넣는게 이해하기가 많이 어려웠다.
중복되는 것을 피하기 위해 set도 사용해보았지만 (1,1,0) 같은 경우가 있어서 생각해보다가 결국은 discuss에 있는 방법을 보았다.
if i > 0 && arr[i] == arr[i - 1] { continue } // 정렬했으므로 중복 제거할수있다
위 코드는 가장 먼저 나오는 중복제거 부분이다.
한번 정렬하고서 순회하면서 후보를 찾아나가는데, 연속해서 같은 값이 들어올 경우 결과값도 동일하므로 제외해야한다.
예) [1,1,2,2,4,4,4] 인 경우
가장 맨 앞의 1에 대해서 경우를 찾아두었다면, 두번째 1도 첫번째 1과 마찬가지로 같은 결과의 쌍들을 갖게 된다.
while left < right && arr[left] == arr[left + 1] { left += 1 } // 중복되는 원소가 안나올때까지 이동 while left < right && arr[right] == arr[right - 1] { right -= 1 } // 중복되는 원소가 안나올때까지 이동 left += 1; right -= 1
위 코드는 두번째로 나오는 중복제거 부분이다.
이 코드는 투포인터 영역에 있는데, 한번 답을 찾았다면 그 다음 left와 right의 각각의 원소가 현재 원소 값과 같다면 결과도 같게 되므로 중복이 발생한다. 이 경우를 피하기 위해 동일한게 나오지 않을 때까지 이동시킨다.
예) [1,1,2,2,3,3,3], target = 4 인 경우
가장 맨 앞의 1과 가장 끝의 3을 가장 먼저 답으로 찾게 된다. 그런데 left의 그 다음도 1이고, right의 앞쪽도 3이라서 중복된 결과를 가져온다. 결과를 저장하는 부분을 ans.append()로 그냥 넣어주고 싶기 때문에 미리 겹치지 않게 잘 넣어야한다.
left는 가장 마지막 중복되는 1 (두번째 1)로 밀어주고, right도 가장 마지막(가장처음으로 나오는)으로 나오는 3으로 밀어주어야 중복없이 넣을 수 있게 된다.
그리고 계속해서 다음번째의 정답을 탐색하기 위해(투포인터) left와 right 모두 각각 이동하는 것도 잊지말자.(left: 1->2), (right: 3->2)
// 제출 코드 class Solution { func threeSum(_ nums: [Int]) -> [[Int]] { if nums.count < 3 { return [] } var ans = [[Int]]() var arr = nums.sorted() for i in (0..<arr.count) { if i > 0 && arr[i] == arr[i - 1] { continue } // 정렬했으므로 중복 제거할수있다 var left = i+1, right = arr.count - 1 let remain = 0 - arr[i] while left < right { let sum = arr[left] + arr[right] if sum == remain { ans.append([arr[i], arr[left], arr[right]]) while left < right && arr[left] == arr[left + 1] { left += 1 } // 중복되는 원소가 안나올때까지 이동 while left < right && arr[right] == arr[right - 1] { right -= 1 } // 중복되는 원소가 안나올때까지 이동 left += 1; right -= 1 } else if sum < remain { left += 1 } else { right -= 1 } } } return ans } }
반응형'프로그래밍 > 코딩테스트' 카테고리의 다른 글
[LeetCode] 19. Remove Nth Node From End of List / Swift (0) 2021.07.06 [LeetCode] 17. Letter Combinations of a Phone Number / Swift (0) 2021.07.06 [LeetCode] 11. Container With Most Water / Swift (0) 2021.07.01 [LeetCode] 5. Longest Palindromic Substring / Swift (0) 2021.07.01 [LeetCode] 3. Longest Substring Without Repeating Characters / Swift (0) 2021.06.30