[백준] 두 수의 합 (카운팅 배열)

문제 소개

두 수의 합 - 백준 3273번 문제를 정리합니다.
이 문제는 수열에서 두 수를 골라 합이 특정 값이 되는 경우의 수를 찾는 문제입니다.
특히 이 문제는 수의 범위가 정해져 있고, 모든 수가 서로 다른 양의 정수라는 조건이 있어서, 카운팅 배열을 이용한 O(n) 풀이가 가능합니다.

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

---

문제 접근 방식

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

1. 수열의 각 수를 인덱스로 사용해 boolean 배열에 존재 여부를 기록
2. 수열을 다시 순회하면서 x - a[i]가 존재 배열에 포함되어 있는지 확인
3. (a, b)와 (b, a)를 각각 세게 되므로 최종 카운트는 2로 나눠서 출력

---

해결 과정 및 코드

핵심 아이디어

1. 수열에 있는 모든 수를 exists[num] = true로 표시
2. 이후 다시 순회하며 target = x - num이 존재하는지를 체크
3. 단, num == target일 경우 자기 자신과 짝을 이루는 것이므로 제외
4. 모든 쌍을 중복으로 세게 되므로 정답은 count / 2 처리
5. 이 방식은 정렬도 필요 없고, 한 번씩만 순회하면 되므로 시간복잡도는 O(n)

코드

시간 복잡도 : O(N)

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		int N = read(); // 수열 크기
		boolean[] exists = new boolean[1_000_001]; // 존재 여부 기록용
		int[] nums = new int[N];

		// 입력 받으면서 존재 체크
		for (int i = 0; i < N; i++) {
			nums[i] = read();
			exists[nums[i]] = true;
		}

		int x = read(); // 목표 합
		int count = 0;

		// 다시 순회하며 x - a[i] 존재 여부 확인
		for (int i = 0; i < N; i++) {
			int target = x - nums[i];

			if (target <= 0 || target > 1_000_000) continue;
			if (exists[target]) count++;
		}

		// (a, b)와 (b, a) 모두 세었으므로 2로 나눠줌 (a==b 인 경우는 최대 1개 뿐이라 / 2로 제거됨)
		System.out.println(count / 2);
	}

	// 빠른 입력 처리
	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;
	}
}