[백준] 3273 : 두 수의 합 - Java

• 백준 문제 URL

---

문제 요약

양의 정수로 이루어진 수열이 주어지고,
두 수를 더했을 때 특정 값 x가 되는 쌍의 개수를 구하는 문제다.

즉,

• 주어진 배열 arr 중에서
• 서로 다른 두 수의 합이 x인 경우의 수를 세면 된다.

---

핵심 아이디어

이 문제는 브루트포스(이중 for문) 로 풀면 시간 복잡도가 (O(n^2))이라
n이 100,000일 때 시간 초과가 발생한다.

따라서 효율적인 방법인 투 포인터(Two Pointer) 기법을 사용한다.

1. 배열을 정렬한다.
2. 왼쪽 포인터(start) 와 오른쪽 포인터(end) 를 양 끝에 두고,
   합이 target과 비교해 크거나 작을 때 포인터를 조정한다.

---

알고리즘 흐름

1. 입력받은 배열을 정렬.
2. startIdx = 0, endIdx = n-1
3. 두 원소의 합을 계산하여
   • 합이 target보다 작으면, startIdx++
   • 합이 target보다 크면, endIdx--
   • 합이 같으면, 카운트 증가 및 startIdx++
4. startIdx < endIdx 동안 반복

---

투 포인터 핵심 로직

• 시작 포인터(startIdx)와 끝 포인터(endIdx)를 통해
  “합이 목표값보다 작으면 start를 오른쪽으로, 크면 end를 왼쪽으로” 이동시킨다.

while (startIdx < endIdx) {
    int sum = arr[startIdx] + arr[endIdx];
    if (sum == target) {
        count++;
        startIdx++;
    } else if (sum < target) {
        startIdx++;
    } else {
        endIdx--;
    }
}

---

전체 코드 (제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        int target = Integer.parseInt(br.readLine());

        int startIdx = 0;
        int endIdx = arr.length - 1;
        int count = 0;

        while (startIdx < endIdx) {
            int sum = arr[startIdx] + arr[endIdx];

            if (sum == target) {
                count++;
                startIdx++;
            } else if (sum < target) {
                startIdx++;
            } else {
                endIdx--;
            }
        }

        System.out.println(count);
    }
}

---

예제 시뮬레이션

예를 들어,

n = 9  
arr = [5, 12, 7, 10, 9, 1, 2, 3, 11]  
target = 13

정렬 후 → [1, 2, 3, 5, 7, 9, 10, 11, 12]

start	end	arr[start] + arr[end]	비교	result
1	12	13	같음	count = 1
2	11	13	같음	count = 2
3	10	13	같음	count = 3
5	9	14	크다 → end--	-
5	7	12	작다 → start++	-

결과: count = 3

---

핵심 포인트 정리

• 배열을 정렬한 후 양 끝 포인터를 이용해 합을 조정
• 시간 복잡도: (O(n log n)) (정렬) + (O(n)) (투 포인터)
• 공간 복잡도: (O(1))