문제

백준 3273번
https://www.acmicpc.net/problem/3273

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

문제의 조건을 만족하는 쌍의 개수를 출력한다.

Code

• 초기 상태(n = 9, 배열: 5, 12, 7, 10, 9, 1, 2, 3, 11, m = 13
  

• start = 0, end = 8 일 경우
  

  • 일치하므로 count를 늘려주고 start도 늘려준다.

• start = 1, end = 8 일 경우
  

  • 일치하지 않으므로 end를 줄여준다.

• start = 1, end = 7 일 경우
  

  • 일치하므로 count를 늘려주고 start도 늘려준다.

• start = 2, end = 7 일 경우
  

  • 일치하지 않으므로 end를 줄여준다.

• start = 2, end = 6 일 경우
  

  • 일치하므로 count를 늘려주고 start도 늘려준다.

• 위와 같이 반복하면 된다.
  

• 최종적으로 count = 3

Java

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

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());  // 서로 다은 양의 정수의 개수

        int[] nums = new int[n];  // 수열
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);  // 투 포인터를 하기 전 정렬
        int x = Integer.parseInt(br.readLine());  // 두 수의 합의 일치 값

        int start = 0;  // 시작 인덳스
        int end = n - 1;  // 끝 인덱스
        int count = 0;  // 일치 개수
        while (start < end) {  // start 인덱스가 end 인덱스보다 클 경우 종료
            // 두 수의 합이 일치하는 경우
            if (nums[start] + nums[end] == x) {
                count++;
            }

            // 두 수의 합이 일치하거나 클 경우
            if (nums[start] + nums[end] <= x) {
                start++;
            } else {
                end--;
            }
        }
        System.out.println(count);
    }
}