[LeetCode] 15. 3Sum 풀이 - 정렬 + Two Pointer (Java)

✔️ 오늘의 리트코드 공부 기록 – 3Sum (Two Pointer와 HashSet 접근 비교)
 

---

 
문제 요약 (3Sum)

정수 배열 nums가 주어졌을 때, 합이 0이 되는 서로 다른 3개의 원소 [a, b, c]를 모두 찾는 문제.
결과 내 triplet은 중복 없어야 함.

 
문제링크: https://leetcode.com/problems/3sum

---

1. 처음 접근 방식: 완전탐색 + 잘못된 이해로 시작했다

✔️ “그냥 모든 조합을 확인하면 되지 않을까?”

 
가장 처음엔 자연스럽게 이렇게 생각했다.

“3개의 원소를 모두 조합해서 확인하면 되지 않을까?”
→ 즉, 완전탐색(Brute Force, O(n³))

 
하지만 이 방식은
시간 복잡도가 O(n³) 로 너무 비효율적이다.

---

❗️그리고 중요한 오해 하나

 
처음엔 이렇게 생각했다.

“배열 순서를 지켜야 하는 줄 알았다”

 
그래서 정렬을 하지 않고 문제를 풀려고 했고,
자연스럽게 더 복잡한 방향으로 가버렸다.

---

🔄 2. 첫 번째 개선 시도: Map 활용 + 조합 줄이기

GPT 에게 아래와 같은 힌트를 얻고 곰곰히 생각해 보았다.

“배열을 그냥 보지 말고, 먼저 한 번 가공하면 O(n³)가 아니라 O(n²)까지 줄일 수 있어!”

 
그리고 이런 생각이 떠올랐다. (이 때까지만 해도 배열 순서를 지켜야 하는 줄 알았다...)

“그럼, 2개까지만 선택하고 필요한 세 번째 숫자가 오른쪽에 존재하는지만 확인하면 되지 않을까?”

---

💡 아이디어

• 배열 순회하면서 <값, 인덱스> 형태로 Map 저장
  • 결국 동일한 값이면 마지막 인덱스가 Map 에 저장될 것
• i, j 두 수를 고른 뒤, Map 으로 부터 -(nums[i] + nums[j])가 오른쪽에 있는지 확인
• 중복은 정렬 후 Set 저장으로 해결

---

코드 (Java)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (n < 3) return res;

        // 값 -> 마지막 인덱스 저장
        Map<Integer, Integer> lastIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            lastIndex.put(nums[i], i);
        }

        Set<List<Integer>> set = new HashSet<>();

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int target = -(nums[i] + nums[j]);

                if (lastIndex.containsKey(target)) {
                    int k = lastIndex.get(target);
                    if (k > j) { // 오른쪽에 있는지 확인
                        List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(triplet); // 중복 방지용 정렬
                        set.add(triplet);
                    }
                }
            }
        }

        res.addAll(set);
        return res;
    }
}

 

하지만 이 방법의 문제점

• 실행 시간 여전히 느림
• Set 넣기 전 정렬이 필요해 코드가 복잡
• 유지보수 난이도 증가

그래서 다른 접근을 찾기 시작했다.

---

🔁 3. Second Approach: Two Sum 아이디어 확장

이전에 풀었던 Two Sum 문제가 떠올랐다.

“i 를 고정하고, 나머지 구간에서
두 수의 합이 -nums[i] 되는지 찾으면 되지 않을까?”

 
그리고 HashSet으로 complement 확인하면 더 빠를 것 같다고 생각했다.
 

코드 (Java)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> res = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int target = -nums[i];
            Set<Integer> dups = new HashSet<>();
            for (int j = i + 1; j < nums.length; j++) {
                int complement = target - nums[j];
                // hashSet 으로 complement 존재여부 판단
                if (dups.contains(complement)) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], complement);
                    Collections.sort(triplet); // ensure consistent order
                    res.add(triplet);
                }
                dups.add(nums[j]);
            }
        }
        return new ArrayList<>(res);
    }
}

 
 
하지만 이 솔루션 또한 Sorting 이 for 문 내부적으로 필요했고, 무엇보다 정렬·중복 처리 문제 때문에 구현 실수가 계속 발생했다.
예를 들어 dups Set을 for문 바깥에 두면 이전 값이 남아 잘못된 결과가 나오기도 했다.

---

🔎 4. 사고 전환

😮그럼 질문을 이렇게 바꿔보자.
👉 “세 수의 합이 0이 되려면 어떤 구조를 이용할 수 있을까?”
👉 “무작정 찾는 대신, 정렬을 활용하면 더 똑똑하게 찾을 수 있지 않을까?”

정답은 바로 정렬 + Two Pointer.

 

배열을 정렬하면 방향성이 생긴다.

• 합이 작으면 → 더 큰 수가 필요하니 left++
• 합이 크면 → 더 작은 수가 필요하니 right--

즉,

“모든 조합을 확인하는 문제”가 아니라 👉 정렬된 배열 위에서 left / right 를 조절하며 합을 수렴시켜 가는 문제로 관점이 바뀐다.

---

💡 핵심 아이디어

• 배열 정렬
• 하나의 수 nums[i]를 고정
• 나머지 구간에서
  • left = i + 1
  • right = nums.length - 1
• 세 수의 합을 계산하고
  • 합이 0보다 작으면 👉 값이 커져야 하므로 left++
  • 합이 0보다 크면 👉 값이 작아져야 하므로 right--
  • 합이 정확히 0이면 👉 정답 triplet 저장 + 중복 제거 후 포인터 이동
• 같은 값이 반복되면 의미 없는 탐색이므로
  → i, left, right 모두 중복을 스킵해 불필요한 탐색 제거

정렬로 “방향성”을 만들고,
Two Pointer 로 “필요한 부분만 탐색”하는 구조다.
그래서 브루트포스처럼 모든 조합을 보지 않아도 된다!

---

 

최종 코드 (Java)

class Solution {

  public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    Set<Integer> dups = new HashSet<>();
    for (int i = 0; i < nums.length - 1; i++) {
      if(i>0 && nums[i]==nums[i-1]) continue; // skip duplicates for i
      int target = -nums[i];
      // find two sum for target
      for(int left = i + 1, right = nums.length - 1; left < right; ) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
          res.add(Arrays.asList(nums[i], nums[left], nums[right]));
          // skip duplicates for left
          while (left < right && nums[left] == nums[left + 1]) left++;
          // skip duplicates for right
          while (left < right && nums[right] == nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
    return res;
  }
}

 

 

📈Time / Space Complexity

• 시간: O(n²)  
• 공간:  O(1)

---

 

📝 이번 문제에서 얻은 깨달음

• 문제를 정확히 읽자 (나는 배열 순서를 유지해야 하는 줄 알고 괜히 더 어렵게 풀었다 😅)
• 처음엔 “세 수를 모두 확인해야 하는 문제”처럼 보이지만, 정렬을 통해 방향성을 만들 수 있다는 걸 깨닫는 게 핵심이었다.
• 문제 핵심은 “중복을 제거하면서 합이 조건을 만족하는지 효율적으로 탐색” 하는 것이다.

 

3sum은

“모든 경우를 확인하는 문제”가 아니라 문제 구조를 이해하고, 패턴/조건을 활용해 탐색을 최소화하는 것이 핵심