백준 - 3273 (Java)

문제

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)

출력

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

예제 입력 1

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1

3

문제접근

2개 원소의 합을 구하여 일치하는 해를 구하면 되는 문제임으로 2개의 포인터를 주어 접근하면 되겠다는 생각이 들었다.

1. 입력 받은 자연수를 배열로 오름차순 정렬한다.
2. loop를 돌면서 가장 작은 값의 인덱스 i , 가장 큰 값의 인덱스 j를 두어 두 수를 합한다.
3. 두개의 값을 합하여 결과를 비교한다.
   • 구하자는 값인 경우 -> i++ j-- answer++
   • 구하고자 하는 값보다 작은 경우 -> i++
   • 구하고자 하는 값보다 큰 경우 -> j--
4. loop는 i와 값이 j의 값보다 크거나 같은 경우 중단하며 answer를 반환한다.

문제풀이

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;
        st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];

        for(int i = 0; i < N; i++) 
            arr[i] = Integer.parseInt(st.nextToken());

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

        Arrays.sort(arr);                //#1

        int answer = 0;

        int i = 0;
        int j = N-1;
        int temp;

        while(i < j) {                    //#2
            temp = arr[i] + arr[j];

            if(temp == sum) {            //#3
                answer++;
                i++;
                j--;
            }else if(temp < sum) {
                i++;
            }else {
                j--;
            }
        }

        bw.write(answer +"");            //#4
        bw.flush();
        br.close();
        bw.close();
    }

}