[코딩테스트] 두 수의 합

문제

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

생각

• 숫자들을 정렬한 뒤, 수열의 맨앞과 맨 뒤로부터 점점 가운데로 오면서 합이 x인 경우를 카운트 하자
  • 숫자의 합이 x보다 크면 오른쪽 끝의 수를 줄여야 하고, x보다 작으면 왼쪽 끝의 수를 늘려야 한다
  • x일 경우 cnt를 늘리고 왼쪽 끝과 오른쪽 끝을 모두 이동시키자
  • lt(왼쪽 끝) < rt(오른쪽 끝) 일 동안 반복
    

코드

    public int getPairCnt(int n, int x, int[] arr) {

        int cnt = 0;
        Arrays.sort(arr);

        int lt = 0, rt = n - 1;

        while (lt < rt) {
            if (arr[lt] + arr[rt] > x) {
                rt--;
            } else if (arr[lt] + arr[rt] < x) {
                lt++;
            } else {
                cnt++;
                lt++;
                rt--;
            }
        }

        return cnt;
    }

정리

• 예전에 비슷한 문제를 봤을 때는 어렵게 느껴졌었는데 투 포인터 알고리즘을 알고 나니 쉽게 느껴졌던 문제이다!

투포인터 알고리즘

• 정렬된 배열이나 리스트에서 두 요소의 합, 차 또는 그 외 특정 요건을 만족하는 요소 쌍을 찾을 때 유용하게 사용
• 모든 가능한 경우의 수를 하나씩 검사하는 부루트 포스 (Brute Force) 방식이나 완전탐색에 비해 시간 복잡도를 줄일 수 있다는 장점

REF

• Olympiad > Balkan Olympiad in Informatics > Junior Balkan Olympiad in Informatics > JBOI 2008 6번