알고리즘 - 세 수의 합
배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.Permalink
| Input | Output |
|---|---|
| [-1,0,1,2,-1,-4] | [[-1,-1,2],[-1,0,1]] |
Solution1 (브루트 포스로 계산) -> 시간초과Permalink
def threeSum(nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 1):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
for k in range(j + 1, len(nums)):
if k > j + 1 and nums[k] == nums[k - 1]:
continue
if nums[i] + nums[j] + nums[k] == 0:
result.append([nums[i], nums[j], nums[k]])
return result
Solution2 (투 포인터로 합 계산)Permalink
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
results.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return results
투 포인트를 사용하기 위해 먼저 입력값을 오름차순으로 정렬시킨다.
i값을 증가시키며 투 포인트를 이용하여 합이 0이 되는 세 숫자를 찾는데
세 숫자의 합이 0 보다 작으면 left 포인트를 오른쪽으로 이동 시키고
0보다 크면 right 포인트를 왼쪽으로 이동시킨다.
합이 0이면 결과를 저장시킨후 left, right를 각각 이동시킨다.
(하나만 이동시켜서는 0이 되지 않으므로 둘 다 이동시킴)
0이 되는 순간 그 다음 값과 같지 않도록 두 포인트를 계속 이동시킨다.
하지 않으면 [-2,0,0,2,2] 테스트 케이스에서 실패함
댓글남기기