[백준] 3273번 - 두 수의 합 (Silver 3)

문제 링크

백준 3273번 - 두 수의 합 (Silver 3)

문제 설명

수열 $a_1, a_2, \cdots, a_n$과 자연수 $x$가 주어져 있을 때, $a_i + a_j = x$인 $(a_i, a_j) (1 \leq i < j \leq n)$ 쌍의 개수를 구한다.

정답 코드 및 설명

투 포인터 알고리즘을 사용한다.
수열을 크기 순으로 정렬하고, $a_i$와 $a_j$를 가리키는 포인터 두 개를 생각하자.

1. 양 끝에서 시작해서 두 수의 합이 $x$보다 크다면 큰 쪽을 작게 만들어야 하니 $j$를 하나 줄인다.
2. 두 수의 합이 $x$보다 작다면 작은 쪽을 크게 만들어야 하니 $i$를 하나 늘린다.
3. 두 수의 합이 정확히 $x$라면, 양쪽 다 한 칸씩 움직일 수 있는데 풀이에서는 $j$를 줄였다.

3번의 경우 바로 다음 단계에서 $i$가 늘어나게 되므로, 결과적으로 $i$를 늘리는 풀이와 동일하다.
$i$가 $j$보다 항상 작아야하므로, while문의 조건으로 $i < j$를 넣었다.

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(br.readLine());
        Arrays.sort(a);
        bw.write(pair(a, x) + "");
        bw.close();
    }

    static int pair(int[] a, int x) {
        int i = 0, j = a.length - 1, count = 0;
        while (i < j) {
            if (a[i] + a[j] == x)
                count++;
            if (a[i] + a[j] >= x)
                j--;
            if (a[i] + a[j] < x)
                i++;
        }
        return count;
    }
}