[백준] 3273번 두 수의 합 java

1. 백준 3273번 문제

1. 문제

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

2. 입력

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

3. 출력

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

2. 문제 해석

(위의 그림 추가 설명)

1. 오름차순으로 정렬을 한 이후에 시작값과 종점값의 합이 작다면 시작부분을 더 큰 수로 index이동을 한다. 그리고 큰 경우에는 종점값의 index를 이동한다.

2. start와 end에 대한 범위값을 구해서 탐색 구간을 줄이고 문제에 충족하는 target값을 탐색한다.

위와 같은 투포인터 알고리즘으로 두수의 합이 문제의 조건에 충족하는 값이 되게 하는 문제입니다.

3. 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.valueOf(st.nextToken());
        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(st.nextToken());
        }

        Arrays.sort(arr); //오름차순 정렬을 해준다.

        int x = Integer.valueOf(br.readLine());
        
        int start = 0; //배열의 시작
        int end = n - 1; //배열의 끝
        int count = 0;
        int sum = 0;

        while(start < end) {
            sum = arr[start] + arr[end];
            
            if(sum == x) {
                count++;
            }
            if(sum <= x) {
                start++;
            }
            else {
                end--;
            }
        }
        System.out.println(count);
    }
}