class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 숫자 3개 더해서 0
# for 돌리면서 투포인터 사용
nums.sort() # 우선 정렬 -> 그래야.. 투포인터 사용가능
res = []
for a in range(len(nums)):
l, r = a+1, len(nums)-1
while l<r: # 같으면 나옴
if nums[a]+ nums[l] + nums[r] == 0:
res.append([nums[a], nums[l], nums[r]])
elif nums[a]+ nums[l] + nums[r] > 0:
r -=1
else: # nums[a]+ nums[l] + nums[r] < 0:
l +=1
return res
지금 코드는 3Sum 문제의 기본 구조는 잘 잡았는데,
중복 제거 로직이 빠져 있어서 '오답'이 나올 수 있어요.
❌ 문제점 요약
- 중복된 a 값에 대해서도 계속 검사하고 있음 → [-1, -1, 2] 같은 조합이 중복해서 나올 수 있음
- 중복된 l 또는 r 값도 고려하지 않음 → 예: [0, 0, 0]이 여러 번 나올 수 있음
✅ 수정된 코드 (정답 + 중복 제거):
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums)):
# 중복된 i 값은 skip
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
"""
# while j<k and k<len(nums)-1: 하면 안됨.
이미 k = len(nums) - 1로 초기화했기 때문에,
k < len(nums) - 1은 **처음부터 False**가 됩니다.
그 결과, while 루프가 한 번도 실행되지 않을 수 있습니다.
"""
while l < r:
total = nums[i] + nums[l] + nums[r]
if total < 0:
l += 1
elif total > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
# 중복된 l, r 피하기 위해 skip
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
# 다음 후보로 이동
l += 1
r -= 1
return res🔍 핵심 아이디어 요약
| 단계 | 설명 |
| 1. 정렬 | 투 포인터 사용 가능하게 만들기 위해 |
| 2. for 루프 | 첫 번째 숫자 nums[i] 고정 |
| 3. 투 포인터 | i+1부터 끝까지 l, r로 탐색 |
| 4. 중복 제거 | nums[i], nums[l], nums[r] 값이 이전과 같으면 skip |
중복제거를 왜 total 이 0 일때만 해? 0보다 작을때랑 클때도 해야하는거 아님?
ChatGPT의 말:
좋은 질문이에요! 😊
겉보기엔 total < 0이나 total > 0일 때도 중복 제거가 필요해 보이지만,
실제로는 total == 0일 때만 중복 제거를 하면 충분해요.
왜 그런지 단계별로 설명할게요.
🔍 핵심 원리: 중복된 결과만 제거하면 됨
우리가 중복 제거를 하는 **진짜 이유는 "결과 조합이 중복되는 걸 막기 위해서"**예요.
즉,
- [-1, 0, 1]
- [-1, 0, 1]
이런 식으로 같은 triplet이 결과에 여러 번 나오는 걸 막는 게 목표죠.
✅ total == 0일 때만 중복 제거를 해도 되는 이유
예시: [ -1, -1, 2 ]
nums = [-1, -1, -1, 2]
- 첫 번째 -1에서 (l, r)이 (1, 3) → [-1, -1, 2] ⬅️ 유효
- 다음 l=2도 -1이니까 중복 → while로 스킵!
이렇게 중복 제거는 유효한 조합을 찾았을 때만 의미가 있어요.
❌ 만약 total < 0이거나 total > 0일 때 중복을 제거하면?
- 이 경우는 아직 정답이 아니에요.
- 그러니 굳이 중복 제거해봤자 "정답 후보도 아니고",
오히려 건너뛴 값이 다음 정답 후보가 될 수도 있어요.
예:
nums = [-2, -1, -1, 0, 1, 2]
- nums[i] = -2
- l = 1, r = 5, total = -1 → l += 1 해야 함
- 여기서 중복 제거한다고 l = 3까지 넘기면 [-2, 0, 2] 같은 조합을 놓칠 수 있음 ❌
🔚 결론
| 조건 | 중복 제거 해야 함? | 이유 |
| total == 0 | ✅ YES | 결과 조합 중복 방지 |
| total < 0 / > 0 | ❌ NO | 정답 아님 → 중복 제거 의미 없음, 오히려 정답을 건너뛸 수도 있음 |
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 숫자 3개 더해서 0
# for 돌리면서 투포인터 사용
nums.sort() # 우선 정렬 -> 그래야.. 투포인터 사용가능
res = []
for a in range(len(nums)):
# 중복된 nums[a] 값 skip
while a>0 and nums[a-1] == nums[a]:
continue
l, r = a+1, len(nums)-1
while l<r: # 같으면 나옴
subSum = nums[a]+ nums[l] + nums[r]
if subSum == 0:
res.append([nums[a], nums[l], nums[r]])
# 같을때 결과 추가 후, 중복 제거 위해, index 옮김
while l<r and nums[l] == nums[l+1]:
l +=1
while l<r and nums[r-1] == nums[r]:
r -=1
# 다음 스텝을 위해 이동
l+=1
r-=1
elif subSum > 0:
r -=1
else: # subSum < 0:
l +=1
return res
지금 코드에서 **시간 제한(TLE)**이 걸리는 가장 큰 이유는
👉 while a > 0 and nums[a-1] == nums[a]: continue 이 무한 루프로 작동하기 때문이에요.
❌ 문제 원인: continue 안에서 a가 증가하지 않음
for a in range(len(nums)):
while a > 0 and nums[a-1] == nums[a]:
continue # ❗️ a는 증가하지 않음 → 무한 루프 가능성이렇게 쓰면 a는 그대로인데 while 조건만 계속 검사해서 빠져나오지 못해요.
→ CPU 무한 루프 발생 → 시간 초과(TLE)
✅ 고치려면 이렇게:
while 대신 if + continue 를 써야 해요:
for a in range(len(nums)):
if a > 0 and nums[a] == nums[a - 1]:
continue→ 이러면 중복된 a 값은 스킵하고, 다음 루프로 넘어가요. (a는 for문이 자동으로 증가시켜 줌)
최종 코드
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 숫자 3개 더해서 0
# for 돌리면서 투포인터 사용
nums.sort() # 우선 정렬 -> 그래야.. 투포인터 사용가능
res = []
for a in range(len(nums)):
# 중복된 nums[a] 값 skip
if a>0 and nums[a-1] == nums[a]:
continue
l, r = a+1, len(nums)-1
while l<r: # 같으면 나옴
subSum = nums[a]+ nums[l] + nums[r]
if subSum == 0:
res.append([nums[a], nums[l], nums[r]])
# 같을때 결과 추가 후, 중복 제거 위해, index 옮김
while l<r and nums[l] == nums[l+1]:
l +=1
while l<r and nums[r-1] == nums[r]:
r -=1
# 다음 스텝을 위해 이동
l+=1
r-=1
elif subSum > 0:
r -=1
else: # subSum < 0:
l +=1
return res
3번째 코드
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 3개 합이 0 되는 조합 추가
# i 는 for index 로, j, k 는 투포인터로
res = []
for i in range(len(nums)):
j, k = i+1, len(nums)-1
while j<len(nums) and j<=k:
total = nums[i]+nums[j]+nums[k]
if total > 0:
k-=1
elif total < 0:
j+=1
else: #total==0
res.append([nums[i], nums[j], nums[k]])
return res
❌ 현재 코드의 문제점
- 정렬을 안 해서 투포인터가 의미 없음
→ 투포인터 기법은 배열이 정렬되어 있어야 방향성을 알 수 있습니다. - 중복 결과 필터링 안함
→ [0,0,0] 같이 같은 조합이 여러 번 나올 수 있음 - j <= k 조건이 이상함
→ j < k가 되어야지 j == k일 땐 의미 없는 조합이 됩니다.
❌ 코드 문제점 요약
- if i-1 > 0 and nums[i] == nums[i-1]:
→ i > 0으로 써야지 제대로 중복 제거가 됩니다.
i-1 > 0이면 i >= 2부터만 비교하게 되어 첫 중복 체크를 놓침. - while nums[k-1] == nums[k]:
→ k-1이 배열 밖으로 나갈 수 있음, k > j 조건을 추가해야 안전 - while nums[j] == nums[j+1]:
→ j+1도 배열 밖 접근 가능성 있음, j < k 조건 필요 - j<len(nums) and j<k
→ j < k 하나만 쓰면 충분하고 더 직관적 - 중복 스킵한 후 j += 1, k -= 1 안 해줌
→ 같은 값 건너뛴 후에도 한 칸 이동은 꼭 필요함
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 3개 합이 0 되는 조합 추가
# i 는 for index 로, j, k 는 투포인터로
# 투 포인터 사용하려면, 정렬이 되어있어야!! <-- 아주 중요!!
nums.sort()
res = []
for i in range(len(nums)):
if i>0 and nums[i] == nums[i-1]: # 이전값이랑 같으면 그냥 넘어감, i==1 부터 검색해야하므로, i>0 임!!
continue
j, k = i+1, len(nums)-1
while j<k: # j != k 되어야해서, j<=k 아니라, j<k 되어야 함
total = nums[i]+nums[j]+nums[k]
if total > 0:
k-=1
elif total < 0:
j+=1
else: #total==0
res.append([nums[i], nums[j], nums[k]])
# 추가했으니, 또 다른 조합 찾아야.
while j<k and nums[k-1] == nums[k]: # k 는 왼쪽으로 가야하는데, 현재값이랑 계속 같으면 스킵
k-=1
while j<k and nums[j] == nums[j+1]: # j 는 오른쪽으로 가야하는데, 현재값이랑 계속 같으면 스킵
j+=1
# 스킵해도 마지막에 옮겨야, 새로운 값이 나옴
k-=1
j+=1
return res'LeetCode > Grind169' 카테고리의 다른 글
| 8. String to Integer (atoi) ☆☆★ (0) | 2025.04.26 |
|---|---|
| 416. Partition Equal Subset Sum: DP로 꼭 풀어야! ☆☆★★★ (0) | 2025.04.26 |
| 53. Maximum Subarray ☆☆★ (0) | 2025.04.23 |
| 543. Diameter of Binary Tree ☆☆★★ Diameter 정의, 리턴값 주의! (0) | 2025.04.23 |
| 409. Longest Palindrome ★ (0) | 2025.04.22 |