백준 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)

출력

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

 

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

---

이 문제는 투 포인터를 이용하면 쉽게 풀 수 있는 문제이다. 

투 포인터를 사용하지 않고 경우의 수를 전부 계산하면 시간초과가 나서 투 포인터를 공부하여 푸는 것이 좋다.

 

투 포인터란 포인터 2개를 이용하여 배열 또는 리스트에서 원하는 값을 찾을 때 사용하는 알고리즘으로 위에서 말한 것처럼 모든 경우의 수를 계산하는 것보다 훨씬 효율적인 알고리즘이다. 두 수의 합의 테스트 케이스를 통해 어떤 방법으로 진행되는지 알아보자.

 

위 문제의 테스트 케이스에서는 수열로 5, 12, 7, 10, 9, 1, 2, 3, 11이 순서대로 주어진다.

그리고 이 수열에서 ai + aj = x 가되는 (ai, aj)의 쌍의 수를 구해야하는데 x = 13으로 주어진다.

수열을 배열(표)로 나타내면 다음과 같다.

index	0	1	2	3	4	5	6	7	8
value	5	12	7	10	9	1	2	3	11
pointer

 

투 포인터를 사용하기 위해 우선 배열을 정렬하고 0번쨰 index에 start라는 포인터를 마지막 index에 end라는 포인터를 만들어줘야한다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer	start								end

 

이렇게 세팅이 끝났으면 바로 알고리즘을 진행할 수 있다. 이번 문제에서의 투 포인터 규칙은 다음과 같다.

(배열을 A라고 하고 설명)

 

    1. A[start] + A[end] == x 면 count를 1증가시킨다.

    2. A[start] + A[end] <= x 면 start를 1증가시킨다.

    3. 만약 2번이 아니라면 end를 1증가시킨다. 

    4. start == end가 되면 count를 출력한다.

 

1번은 x가 되는 A[i] + A[j]를 찾았으니 count를 증가시키는 것이다.

2번은 x보다 작거나 같은 A[i] + A[j]를 갖고 있으므로 start를 증가시켜 A[i] + A[j]의 값을 늘리는 것이다.

3번은 2번이 아닐 떄 A[i] + A[j]를 감소시켜야 하므로 end를 감소시킨다. 

 

그러면 실제로 포인터를 움직이며 확인해보자.

 

1)  맨 처음엔 A[start] + A[end] = 1 + 12 = 13이므로 1번에 해당한다.

따라서 count = 1이되고 2번에도 해당하므로 start = 1이 된다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer		start							end

 

2)  다음으로  A[start] + A[end] = 2 + 12 = 14이므로 3번에 해당한다. 따라서 end = 7이 된다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer		start						end

 

3) 다음으로  A[start] + A[end] = 2 + 11 = 13이므로 1번에 해당한다.

따라서 count = 2이되고 2번에도 해당하므로 start = 2이 된다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer			start					end

 

4) 다음으로  A[start] + A[end] = 3 + 11 = 14이므로 3번에 해당한다. 따라서 end = 6이 된다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer			start				end

 

3) 다음으로  A[start] + A[end] = 3 + 10 = 13이므로 1번에 해당한다.

따라서 count = 3이되고 2번에도 해당하므로 start = 3이 된다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer				start			end

 

4) 다음으로  A[start] + A[end] = 5 + 10 = 15이므로 3번에 해당한다. 따라서 end = 5가 된다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer				start		end

 

5) 다음으로  A[start] + A[end] = 5 + 9 = 14이므로 3번에 해당한다. 따라서 end = 4가 된다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer				start	end

 

6) 마지막으로 A[start] + A[end] = 5 + 7 = 12이므로 2번에 해당한다. 따라서 start = 4가 된다.

이제 start == end가 되었으므로 4번에 해당해 탐색이 끝나고 count = 3을 출력한다.

index	0	1	2	3	4	5	6	7	8
value	1	2	3	5	7	9	10	11	12
pointer					start end

 

이런 간단한 규칙으로 우리는 쉽게 A[i] + A[j] = x가 되는 쌍의 개수를 찾을 수 있다.

실제로 어렵지도 않고 시간복잡도가 O(N)이므로 굉장히 빠른 알고리즘이라 언제 써야할지 잘 판단할 수 있다면 유용하게 쓰일 것이다.

 

코드는 다음과 같다.

import java.io.*;
import java.util.*;
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[] A = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            A[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(A);
        int x = Integer.parseInt(br.readLine());
        int start = 0;
        int end = n - 1;
        long count = 0;
        while (start < end){
            if (A[start] + A[end] == x) count++;
            if (A[start] + A[end] <= x) start++;
            else end--;
        }
        System.out.println(count);
    }
}