[백준 1253] 좋다 (Java) - 투 포인터의 심화

🚀 문제 핵심

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다(GOOD)"라고 합니다. 그런 수의 개수를 구하는 문제입니다.

• 데이터 범위: $N \le 2,000$
• 값의 범위: 각 수의 절댓값은 10억 이하

---

💡 해결 전략: 왜 투 포인터인가?

1. 값의 범위 (10억): 이전 '주몽' 문제처럼 배열 인덱스를 활용한 해시 전략은 불가능합니다. $10^9$ 크기의 배열을 만들면 메모리 초과가 발생하기 때문입니다.

2. 시간 복잡도: $N$이 2,000이므로, 각 숫자마다 투 포인터($O(N)$)를 수행하면 전체 $O(N^2)$에 해결 가능합니다. $2000^2 = 4,000,000$으로 1초 제한 내에 충분히 통과할 수 있습니다.

---

⚠️ 주의해야 할 함정: "자기 자신 제외"

이 문제에서 가장 실수하기 쉬운 부분은 "다른 수 두 개의 합"이라는 조건입니다. 판별 대상이 되는 '자기 자신'의 인덱스는 합을 구하는 두 포인터에서 반드시 제외해야 합니다.

• j == i: 왼쪽 포인터가 판별 대상과 같다면 다음 칸으로 이동
• k == i: 오른쪽 포인터가 판별 대상과 같다면 이전 칸으로 이동

---

💻 구현 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }

            // 1. 투 포인터를 위한 정렬
            Arrays.sort(nums);

            int count = 0;
            // 2. 각 숫자가 '좋은 수'인지 판별 (N번 반복)
            for (int i = 0; i < n; i++) {
                int target = nums[i];
                int j = 0, k = n - 1; // 양 끝단에 포인터 배치

                while (j < k) {
                    // 예외 처리: 다른 두 수의 합이어야 하므로 자기 자신은 제외
                    if (j == i) { j++; continue; }
                    if (k == i) { k--; continue; }

                    int sum = nums[j] + nums[k];

                    if (sum == target) {
                        count++;
                        break; // '좋은 수'임이 확인되면 즉시 종료
                    } else if (sum < target) {
                        j++;
                    } else {
                        k--;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

---

🧐 설계 포인트

1. 정렬의 중요성: 투 포인터를 사용하기 위해 $O(N \log N)$의 정렬은 필수입니다. 정렬된 상태에서 sum과 target을 비교하며 포인터를 좁혀가는 논리가 핵심입니다.

2. 음수 값의 존재: 값의 범위에 음수가 포함되어 있어도 투 포인터 로직은 동일하게 작동합니다. 다만, 음수가 섞여 있어 합의 증감이 직관적이지 않을 수 있으나 정렬된 상태라면 포인터 이동 원칙은 변하지 않습니다.

---

🎯 마치며

값의 범위가 매우 커서 해시를 사용할 수 없을 때, 정렬 후 투 포인터를 사용하는 방식은 매우 강력한 대안이 됩니다. 특히 이번 문제처럼 특정 인덱스를 제외해야 하는 예외 조건이 붙을 때 당황하지 않고 포인터를 제어하는 연습이 중요합니다.