Live of Thinking

다음과 같은 문제를 생각해 보자.

$n$개의 서로 다른 정수가 주어질 때, 여기서 서로 다른 두 수를 골라서 합이 $x$가 되게 만드는 경우의 수를 구하시오.

이 문제의 경우 입력되는 정수의 범위가 크지 않아서 크기가 $10^6$인 배열을 선언해서 각 수가 등장했는지 체크하는 식의 방법으로 풀 수 있다. 하지만 입력되는 정수의 범위가 $10^{18}$ 정도까지 커졌다고 가정해 보자. 일단 set 등을 사용해서 각 수마다 $x$에서 그 수를 뺀 값이 set에 존재하는지 확인하는 방식으로 해결이 가능하다. 하지만 set은 속도가 그렇게 빠르지 않고, 각 수마다 set에서 값을 찾는 시간복잡도가 $O(\lg n)$이다. 이번 글에서는 이 방법을 대체할 수 있는 투 포인터(Two Pointers)에 대해 다룬다.

서로 다른 두 수를 고를 때 수들의 순서가 어떻게 되어 있는지는 중요하지 않다. 이렇게 수들의 순서가 중요하지 않은 경우 일단 정렬을 하자. 그러면 풀이가 보이는 경우가 많다. 이런 문제도 그런 경우 중 하나인데, 두 수를 고를 수열이 다음과 같고 쌍의 개수를 구해야 하는 합이 $22$라고 하자.

$$[4, 7, 12, 6, 15, 3, 19, 17, 10]$$

이걸 정렬하면

$$[3, 4, 6, 7, 10, 12, 15, 17, 19]$$

이렇게 된다. 이제 투 포인터를 어떻게 적용하는지 알아보자. 먼저 이 수열에서 두 수를 골라서 합이 $22$가 되는 경우의 수는 $3$이다. 여기서 가능한 경우를 나열해 보면

$$[\color{red}{3}, 4, 6, 7, 10, 12, 15, 17, \color{red}{19}]$$

$$[3, 4, 6, \color{red}{7}, 10, 12, \color{red}{15}, 17, 19]$$

$$[3, 4, 6, 7, \color{red}{10}, \color{red}{12}, 15, 17, 19]$$

이렇게 된다. 합이 일정하기 때문에 고른 수 중 작은 수가 커지면 큰 수는 작아지며, 수열이 오름차순으로 정렬되어 있기 때문에 가능한 경우 중 아무거나 둘을 비교했을 때 작은 수가 상대적으로 뒤에 나올 경우 큰 수는 상대적으로 앞에 나오는 것을 알 수 있다. 즉 어떤 가능한 쌍 $(a_i, a_j)$를 찾았고(여기서 $a_i < a_j$라고 가정한다. 따라서 $i < j$이다.) 그 다음으로 $(a_{i + 1}, a_k)$가 가능한 쌍이 되는 $k$가 존재하는지 확인할 경우 $j$보다 큰 값들은 $k$의 후보가 될 수 없다. 따라서 $i$를 증가시킬 때 $j$를 계속 감소시키면서 가능한 쌍이 있는지 확인하면 된다. 이렇게 $i$와 $j$라는 두 인덱스(포인터)를 움직이면서 답을 구하기 때문에 이 방법을 투 포인터라고 부른다. 그러면 포인터 $i$와 $j$를 어떤 순서로 움직여야 할지를 알아야 하는데, 이를 위에 나온 예시의 설명을 통해 알아보기로 한다.

먼저 포인터를 수열의 양쪽 끝에 둔다. 편의상 첫 번째 수에 있는 포인터를 $\color{red}{\text{A}}$, 마지막 수에 있는 포인터를 $\color{blue}{\text{B}}$라고 하자.

$$[\color{red}{3}, 4, 6, 7, 10, 12, 15, 17, \color{blue}{19}]$$

두 포인터가 가리키는 수의 합을 확인한다. 이 경우 처음부터 합이 $22$와 일치하므로 가능한 경우의 수에 $1$을 더한다. 다음으로 포인터를 움직이는데, 합이 $22$보다 작다면 $\color{red}{\text{A}}$를 다음 위치로 옮기고, 합이 $22$보다 크다면 $\color{blue}{\text{B}}$를 이전 위치로 옮긴다. 지금처럼 합이 $22$인 경우는 둘 중 어느 쪽을 선택해도 된다. 여기서는 $\color{red}{\text{A}}$를 다음 위치로 옮겼다고 하자.

$$[3, \color{red}{4}, 6, 7, 10, 12, 15, 17, \color{blue}{19}], \text{ans} = 1$$

포인터가 가리키는 수들의 합이 $22$보다 크므로 이번에는 $\color{blue}{\text{B}}$를 이전 위치로 옮긴다.

$$[3, \color{red}{4}, 6, 7, 10, 12, 15, \color{blue}{17}, 19], \text{ans} = 1$$

포인터가 가리키는 수들의 합이 $22$보다 작으므로 $\color{red}{\text{A}}$를 다음 위치로 옮긴다.

$$[3, 4, \color{red}{6}, 7, 10, 12, 15, \color{blue}{17}, 19], \text{ans} = 1$$

이 과정을 반복한다.

$$[3, 4, \color{red}{6}, 7, 10, 12, \color{blue}{15}, 17, 19], \text{ans} = 1$$

$$[3, 4, 6, \color{red}{7}, 10, 12, \color{blue}{15}, 17, 19], \text{ans} = 2$$

$$[3, 4, 6, 7, \color{red}{10}, 12, \color{blue}{15}, 17, 19], \text{ans} = 2$$

$$[3, 4, 6, 7, \color{red}{10}, \color{blue}{12}, 15, 17, 19], \text{ans} = 3$$

$$[3, 4, 6, 7, 10, \color{red}{1}\color{blue}{2}, 15, 17, 19], \text{ans} = 3$$

두 포인터가 같은 위치에 왔을 경우 모든 경우를 다 확인한 것이므로 여기서 탐색을 종료하면 된다. 포인터를 움직이는 횟수가 $n$을 넘지 않으므로 시간복잡도는 $\Theta(n)$이 된다. 계속 탐색을 하면 가능한 경우를 또 찾을 수도 있지만, 그 경우들은 이미 앞에서 다 찾았고 단지 $(a_i, a_j)$에서 $(a_j, a_i)$로만 바뀐 것이므로 순서가 중요하지 않은 경우 의미가 없다.

이제 이런 방식으로 정렬된 수열에서 투 포인터로 조건에 맞는 쌍의 개수를 선형 시간에 구할 수 있다. 구현은 다음과 같다.

int n, a[100005]; // a 배열의 원소는 오름차순으로 정렬되어 있다고 가정한다.
int f(int x)
{
    int s = 0;
    for(int i = 1, j = n; i < j;)
    {
        if(a[i] + a[j] == x)s++;
        if(a[i] + a[j] <= x)i++;
        else j--;
    }
}

[연습문제]

BOJ 11728. 배열 합치기 (Silver V)

양쪽 배열에 포인터를 하나씩 에서 가장 작은 값부터 차례로 출력한다. 다만 $(N + M)$개의 정수를 다 입력받고 전체를 정렬하는 풀이도 충분히 빠르게 통과한다고 하니 참고하자.

BOJ 2467. 용액 (Gold V)

양 끝에서부터 포인터를 가운데로 움직이면서 합이 $0$에 가장 가까운 조합을 찾는다. 합이 양수일 때는 양수 쪽에 있는 포인터를, 합이 음수일 때는 음수 쪽에 있는 포인터를 움직이면 된다.

BOJ 2470. 두 용액 (Gold V)

특성값을 정렬해야 하는 점만 빼면 2467번과 차이는 없다.

BOJ 1806. Subsequence (Gold IV)