✅ 문제 - 세 수의 합
![](https://blog.kakaocdn.net/dn/Fmsek/btsCWKGeZ5k/HfqLZkHlJptwtOwBMcgiw1/img.png)
💡 숫자로 이루어진 리스트의 값 3개를 더했을 때 0이 되는 세 수를 구하는 문제
✅ 첫 번째 시도 - 런타임 초과
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
#i,j,k 세 수의 합
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:
results.append([nums[i], nums[j], nums[k]])
return results
💡 내가 잡은 Point
1. 리스트 오름차순 정렬
2. 세 수 i, j, k 비교
3. 세 수는 중복값이 될 수 없음
여기서 문제점
for문을 세 번이나 중첩해서 쓰니까 당연히 런타임 에러가 난다. 시간복잡도가 O(N^3) 인 셈.
✅ 두 번째 시도 - 런타임 초과
solution) 투 포인터 사용
💡투 포인터란? 두 기준점을 잡아(보통은 양 끝) 범위를 점점 좁혀나가며 확인하는 방식
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
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: #합이 0보다 작으면 값이 더 커야하므로 오른쪽으로 이동
left+=1
elif sum>0: #합이 0보다 크면 값이 더 작아야 하므로 왼쪽으로 이동
right-=1
else:
results.append([nums[i], nums[left], nums[right]])
return results
중복값 제외하는 것 까지는 똑같고 3개의 중첩 for문 대신 투 포인터 이용하여 left, right를 지정해서 합을 구했는데도 런타임 초과다. 맞는 것 같은데 도저히 답을 모르겠어서 다른 사람들의 풀이를 보니 앞에서 중복값 제거가 한번 더 필요하다.
첫 번째로 걸었던 중복값은 바로 앞뒤에 연달아 붙은 값을 비교해서 같은 경우는 넘어가는 것이고,
두 번재 걸어야 할 중복값은 left, right가 이동하면서 같은 값일 경우를 제외하기 위해서다.
예를들어 [-3, -2, -2, 0, 1, 2, 2, 3] 일 경우 [-2, 0, 2]가 두 번 나올 수 있다.
따라서 포인터의 앞 뒤 값이 같을 경우는 스킵하고 포인터를 계속해서 다음으로 이동시켜 주면 된다.
while left<right and nums[left] == nums[left+1]:
left += 1
while left<right and nums[right] == nums[right-1]:
right -= 1
# while문이 false일 경우 포인터 이동
left += 1
right -= 1
while문 밖에서 포인터를 또 이동시켜주는 이유는,
포인터와 비교하는 수가 달라지게 되면 멈추기때문에 한번 더 이동을 해서 sum을 비교해야하기 때문이다.
전체 코드
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
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: #합이 0보다 작으면 값이 더 커야하므로 오른쪽으로 이동
left+=1
elif sum>0: #합이 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
'++ > 자료구조&알고리즘' 카테고리의 다른 글
[baekjoon] 9012. 괄호 (3) | 2024.01.04 |
---|---|
[Leetcode] 20. Valid Parentheses (0) | 2024.01.04 |
[Leetcode] 5. Longest Palindromic Substring (0) | 2024.01.03 |
[Leetcode] 49. Group Anagrams (0) | 2024.01.03 |
[Leetcode] 561. Array Partition (0) | 2023.12.19 |