문제 설명#
3Sum - LeetCode
📌 문제 설명#
주어진 배열 nums에서 합이 0이 되는 세 개의 숫자 조합(삼중합, triplets) 을 모두 찾는 문제입니다.
✅ 조건:
- 각 조합은 중복 없이 한 번만 포함되어야 합니다.
- 시간 복잡도 O(n²) 이하로 최적화 해야 합니다.
- 입력 배열의 원소는 중복될 수 있음
✅ 예제 1#
1
| nums = [-1, 0, 1, 2, -1, -4]
|
🔹 출력:
1
| [[-1, -1, 2], [-1, 0, 1]]
|
✔ (-1, -1, 2)
✔ (-1, 0, 1)
📌 중복된 (-1, -1, 2)는 한 번만 포함!
💡 접근 방법#
- 정렬 (Sorting)
- 배열을 먼저 정렬하면 중복된 조합을 쉽게 제거할 수 있음.
- 이후 투 포인터(Two Pointer) 기법을 활용하여 효율적으로 탐색
- 투 포인터 (Two Pointer)
i번째 숫자를 고정하고, **나머지 두 숫자(합이 -nums[i])**를 찾음left, right 포인터를 조정하며 탐색
🎯 최적화 전략#
- 정렬하여 중복을 쉽게 제거
- 투 포인터를 활용해 O(n²)으로 탐색 최적화
- 중복된 값은
continue 및 while문으로 스킵
📌 3Sum 문제는 Two Sum의 확장 문제로, 유사한 문제 해결 시에도 매우 유용한 패턴! 🚀
코드 풀이#
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| def threeSum(nums):
nums.sort() # 배열 정렬
result = []
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:
total = nums[i] + nums[left] + nums[right]
if total < 0: # 합이 작으면 left 증가
left += 1
elif total > 0: # 합이 크면 right 감소
right -= 1
else: # 합이 0이면 정답
result.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 result
|
Javascript#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| var threeSum = function(nums) {
nums.sort((a, b) => a - b); // 배열 정렬
let result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // 중복 제거
let left = i + 1, right = nums.length - 1;
while (left < right) {
let total = nums[i] + nums[left] + nums[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
result.push([nums[i], nums[left], nums[right]]);
// 중복 제거
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
}
}
}
return result;
};
|
참고 및 출처#
programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform