[백준] 두 수의 합

 

문제

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)

 

출력

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

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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());
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str);
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<n; i++) {
            list.add(Integer.valueOf(st.nextToken()));
        }
        int x = Integer.parseInt(br.readLine());

        Collections.sort(list);

        int left = 0;
        int right = n-1;
        int count = 0;

        while(left < right) {
            int sum = list.get(left) + list.get(right);
            if(sum > x)
                right--;
            else if(sum < x)
                left++;
            else {
                count++;
                left++;
                right--;
            }
        }

        System.out.println(count);

        br.close();
    }
}

 

수열을 입력받아 정렬 후 투포인터를 사용해 짝의 개수를 구하였다. 리스트의 양쪽 끝부터 계산하여 합이 x보다 크면 right의 값을 줄이고, 합이 x보다 작으면 left의 값을 늘리는 방식으로 구현하였다. 시간 제한을 확인하지 못하고 짝의 개수를 구하는 방식을 단순히 for문을 사용하여 O(n)으로 풀었더니 시간 초과가 일어났던 문제가 있었다.

 

 

출처: 백준, https://www.acmicpc.net/problem/3273