[백준] 두 수의 합 (투포인터)

문제 소개

두 수의 합 - 백준 3273번 문제를 정리합니다.
이 문제는 주어진 수열에서 두 수를 골라 합이 특정 값이 되는 경우의 수를 구하는 투 포인터 유형의 문제입니다.
핵심은 정렬된 배열에서 양쪽 끝에서 좁혀가는 방식으로 효율적으로 조건을 만족하는 쌍을 찾는 것입니다.

문제 링크: 두 수의 합 - 백준 3273번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 정렬 후 투 포인터 기법을 사용하여 양쪽 끝에서 포인터를 이동
2. 합이 목표보다 작으면 왼쪽 포인터 증가, 크면 오른쪽 포인터 감소
3. 합이 목표와 같으면 카운트 증가 후 왼쪽 포인터 증가
4. 모든 원소가 서로 다른 양의 정수이므로 중복 쌍에 대한 처리를 따로 고려하지 않아도 됨

---

해결 과정 및 코드

핵심 아이디어

1. 수열을 정렬한 뒤, 가장 작은 수(left)와 가장 큰 수(right)에서 시작
2. nums[left] + nums[right]가 x와 같다면 조건 만족 → cnt++
3. 합이 작다면 더 큰 수를 만들기 위해 left++
4. 합이 크다면 더 작은 수를 만들기 위해 right--
5. 이때 모든 수가 서로 다르기 때문에 같은 값이 두 번 등장해 생기는 중복 쌍을 걱정할 필요가 없음

코드

시간 복잡도 : O(n log n)
이유: 정렬에 O(n log n), 투 포인터 탐색에 O(n)

 

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		int N = read(); // 수열의 크기
		ArrayList<Integer> nums = new ArrayList<>(N);
		for (int i = 0; i < N; i++) {
			nums.add(read()); // 수열 입력
		}
		int x = read(); // 목표 합

		Collections.sort(nums); // 정렬

		int left = 0, right = nums.size() - 1, cnt = 0;

		while (left < right) {
			int sum = nums.get(left) + nums.get(right);
			if (sum == x) cnt++; // 조건 만족 → 개수 증가
			if (sum <= x) left++; // 합이 작으면 더 큰 수 필요
			else right--; // 합이 크면 더 작은 수 필요
		}

		System.out.println(cnt); // 정답 출력
	}

	// 빠른 입력을 위한 메서드
	public static int read() throws IOException {
		int cur, n = System.in.read() & 15;
		boolean isNegative = (n == 13);
		if (isNegative) n = System.in.read() & 15;
		while ((cur = System.in.read()) > 32) {
			n = (n << 3) + (n << 1) + (cur & 15);
		}
		return isNegative ? -n : n;
	}
}