[백준 1940] 주몽 (Java) - 투 포인터 vs 해시

🚀 문제 핵심

N개의 고유한 재료 번호가 주어질 때, 두 번호의 합이 M이 되는 쌍의 개수를 구하는 문제입니다.

• 데이터 범위: $N \le 15,000$, $M \le 10,000,000$
• 특이사항: 재료 번호는 10만 이하의 자연수입니다.

---

💡 풀이 1. 투 포인터 (Two Pointers)

배열을 정렬한 뒤, 양 끝에서 포인터를 좁혀오며 합을 체크하는 방식입니다.

• 원리:
  • sum == M: 쌍을 찾았으므로 양쪽 포인터를 모두 안쪽으로 이동합니다.
  • sum < M: 합을 키워야 하므로 왼쪽 포인터(i)를 오른쪽으로 이동합니다.
  • sum > M: 합을 줄여야 하므로 오른쪽 포인터(j)를 왼쪽으로 이동합니다.
• 시간 복잡도: 정렬 $O(N \log N)$ + 탐색 $O(N) = \mathbf{O(N \log N)}$

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_BOJ_1940_two_pointer {

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());
            int m = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }

            // 정렬 후 양 끝 포인터 전략
            Arrays.sort(nums);

            int i = 0, j = nums.length - 1, count = 0;
            while (i < j) {
                int sum = nums[i] + nums[j];

                if (sum == m) {
                    count++;
                    i++;
                    j--;
                } else if (sum < m) {
                    i++;
                } else {
                    j--;
                }
            }

            System.out.println(count);
        }
    }
}

---

💡 풀이 2. 해시/배열 인덱스 활용 (Hash-like)

재료 번호의 최대 범위(10만)가 크지 않다는 점을 이용해, 방문 여부를 기록하며 즉시 짝을 찾는 방식입니다.

• 원리: 현재 값 num이 들어올 때, 합이 M이 되기 위해 필요한 target($M - num$)이 이전에 등장했는지 확인합니다.
• 시간 복잡도: 배열 순회 1회 = $\mathbf{O(N)}$
• 공간 복잡도: $O(100,001)$

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());
            int m = Integer.parseInt(br.readLine());

            // 등장 여부 기록을 통한 O(N) 풀이
            StringTokenizer st = new StringTokenizer(br.readLine());
            boolean[] appear = new boolean[100001];
            int count = 0;
            for (int i = 0; i < n; i++) {
                int num = Integer.parseInt(st.nextToken());
                int target = m - num;
                if (target >= 0 && target <= 100000 && appear[target]) {
                    count++;
                }
                appear[num] = true;
            }

            System.out.println(count);
        }
    }
}

---

🧐 기술적 통찰: 어떤 방식이 더 우수할까?

비교 항목	투 포인터 (정렬)	해시 (배열 인덱스)
시간 복잡도	$O(NlogN)$	$O(N)$ (매우 빠름)
공간 복잡도	$O(1)$ (추가 공간 거의 없음)	$O(Range \ of \ values)$ (메모리 사용)
범용성	값의 범위가 커도 정렬만 되면 가능	값의 범위가 작을 때만 효율적

이번 문제처럼 $N$이 작고 값의 범위도 제한적일 때는 해시 방식이 압도적으로 빠르지만, 만약 재료 번호가 10억 단위였다면 투 포인터가 유일한 해답이 되었을 것입니다. 상황에 맞는 적절한 Trade-off를 고민하는 것이 중요합니다.

---

🎯 마치며

연속된 수열이 아닌 '두 수의 합'을 찾을 때, 정렬을 통한 투 포인터 접근은 매우 강력한 무기입니다. 동시에 문제의 제약 조건을 파악해 공간을 활용한 최적화를 시도해 보는 습관은 실제 코딩 테스트에서 큰 차이를 만듭니다.