3273번: 두 수의 합

문제

n개의 서로 다른 양의 정수로 이루어진 수열이 주어졌을 때, $a_i + a_j = x$ (1 ≤ i < j ≤ n)을 만족하는 쌍의 수를 구하는 문제입니다.

• 입력: 첫째 줄에 수열의 크기 n이 주어집니다. 둘째 줄에 수열에 포함되는 수가 주어집니다. 셋째 줄에는 x가 주어집니다.
• 출력: 문제의 조건을 만족하는 쌍의 개수를 출력합니다.

링크: https://www.acmicpc.net/problem/3273

풀이 1: 정렬과 투 포인터

배열을 오름차순으로 정렬한 뒤, 양 끝에서부터 포인터를 좁혀오며 합을 찾는 정석적인 투 포인터 풀이입니다.

1. 정렬: 배열 a를 오름차순으로 정렬합니다. 시간 복잡도는 O(N log N)이 소요됩니다.
2. 투 포인터 탐색: 시작 포인터 s를 0, 끝 포인터 e를 n - 1로 설정합니다.
   • a[s] + a[e] == x: 두 수의 합이 x와 같다면 쌍을 찾은 것이므로 정답(ans)을 1 증가시키고, 다음 쌍을 찾기 위해 시작 포인터 s를 1 증가시킵니다.
   • a[s] + a[e] < x: 합이 x보다 작다면 값을 키워야 하므로 시작 포인터 s를 우측으로 이동시킵니다.
   • a[s] + a[e] > x: 합이 x보다 크다면 값을 줄여야 하므로 끝 포인터 e를 좌측으로 이동시킵니다.

코드 1

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

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

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

       // 투 포인터를 사용하기 위해 반드시 정렬 수행
       Arrays.sort(a);
       
       int s = 0, e = n - 1;
       int ans = 0;
       
       while (s < e) {
          if (a[s] + a[e] == x) {
             ans++;
             s++; // e-- 를 수행하거나 s++ 둘 중 하나를 수행하여 포인터를 이동
          } else if (a[s] + a[e] < x) {
             s++;
          } else {
             e--;
          }
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

풀이 2: 방문 배열(Boolean Array)을 활용한 최적화

이 문제는 수열의 숫자 최댓값과 구해야 하는 합 x의 최댓값(2,000,000)이 제한적이라는 특징이 있습니다. 이를 이용하여 정렬 없이 배열의 인덱스를 직접 조회하는 O(N) 풀이입니다. 속도가 투 포인터 방식보다 훨씬 빠릅니다.

1. 방문 배열 생성: 크기가 2,000,001인 boolean 배열 check를 선언하고, 수열을 입력받으면서 등장한 숫자를 인덱스로 삼아 true로 체크합니다.
2. O(N) 탐색: 1부터 (x + 1) / 2 미만까지 반복문을 돕니다.
   • 절반까지만 탐색하는 이유: i와 x - i를 동시에 확인하기 때문에 끝까지 탐색하면 같은 쌍을 2번 카운트하게 됩니다. 또한 반복문의 조건을 < (x + 1) / 2로 설정함으로써 i + i = x가 되는(서로 다른 수여야 한다는 조건 위배) 예외를 완벽히 차단합니다.
3. check[i]와 check[x - i]가 모두 true라면, 합이 x가 되는 두 수가 모두 수열에 존재한다는 의미이므로 정답(ans)을 1 증가시킵니다.

코드 2

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

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

        int n = Integer.parseInt(br.readLine());

        int[] a = new int[n];
        boolean[] check = new boolean[2000001]; // x의 최댓값 범위에 맞춘 방문 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
            check[a[i]] = true; // 등장한 숫자를 true로 마킹
        }

        int x = Integer.parseInt(br.readLine());
        int ans = 0;
        
        // 절반까지만 탐색하여 중복 카운트 방지 및 i * 2 == x 인 상황 배제
        for (int i = 1; i < (x + 1) / 2; i++) {
            // i와 x-i 가 모두 배열에 존재한다면 쌍이 성립됨
            if (check[i] && check[x - i])
                ans++;
        }

        bw.write(ans + "");
        bw.flush();
        bw.close();
        br.close();
    }
}

알고리즘 분류

정렬 (Sorting), 투 포인터 (Two Pointers), 배열을 이용한 탐색