- 3Sum
링크텍스트
합해서 0이 되는 세 개의 수로 이루어진 배열을 반환하는 문제이다. 첫날 문제였는데 너무 어려웠다.
파이썬도 거의 처음 접해보는 것이나 마찬가지였다.
준비되지 않은 나에게 노홍철처럼 다가온 문제.. 그래서 다시 정리한다.
투포인터를 이용해서 푸는 문제이다.
nums = [-2, 0, 1, 1, 2]
nums = sorted(nums) # (중요) 오름차순으로 정렬
output = []
for i, el in enumerate(nums):
left = i + 1
right = len(nums) - 1
while left < right:
if el + nums[left] + nums[right] > 0:
right -= 1
elif el + nums[left] + nums[right] < 0:
left += 1
else:
output.append([el, nums[left], nums[right])
left += 1
right -= 1
# 중복 제거
tuple_arr = [tuple(i) for i in output] # 1. 튜플로 변환해주어야 한다.
unique_arr = [list(i) for i in set(tuple_arr)] # 2. set을 통해 중복을 제거먼저 배열을 오름차순으로 정리한다.
배열을 순회하면서 해당 요소(el)와 left(해당 요소 다음의 요소를 가리키는 인덱스), right(배열의 마지막 요소를 가리키는 인덱스)의 합이 0이 되는지 확인한다.
이 세 값의 합이 0보다 크다면 right를 하나 감소시킨다.
이 세 값의 합이 0보다 작다면 left를 하나 증가시킨다.
이 세 값의 합이 0이라면 결과 배열에 추가해주고 left를 하나 증가, right를 하나 감소시킨다.
그리고 원래의 nums 배열에는 중복된 요소들이 존재하기 때문에 결과 배열에도 (그 순서는 다르지만) 내용이 중복된 요소들이 있을 수 있기 때문에 이를 제거해준다.
중복 제거는 set을 사용한다.
이때 리스트를 tuple로 변환해준 뒤, set으로 변환한다.
set을 적용하기 전에 tuple로 변환해주어야 하는 이유는: https://herjh0405.tistory.com/68
