[알고리즘] 투포인터 - 백준 2230: 수 고르기, 백준 1806: 부분합

[실전 알고리즘] 0x14강 - 투 포인터

바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.

---

투포인터 알고리즘은 배열에서 원래 이중 for문으로 O(N^2)으로 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 어떻게 N이나 줄일 수 있냐면, 일반적인 이중 for문에서 i = 0일 때 j가 0부터 n-1까지 돌고, i = 1일 때 j가 0부터 n-1까지 도는 방식, 즉 각 i에 대해서 j가 0부터 n-1까지 도는 상황을 생각해보면, i = 0일 때 계산하면서 얻은 정보가 i = 1일 때에 전혀 쓰이지가 않는다. 그런데 투 포인터에서는 i = 0일 때 계산하면서 얻은 정보를 i = 1일 때 활용한다. 그 정보가 포인터의 이동으로 나타나는 것이다. 바로 문제로 보자.

 

백준 2230: 수 고르기

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

수열에서 두 수를 골랐을 때 그 차이가 M 이상이면서 제일 작은 경우를 구하면 된다. 이전 이분 탐색에서 풀었던, 합이 0 되는 두 수 찾기와 거의 똑같다. lower_bound(~, ~, x + M)을 돌리면 된다. 이를 투 포인터로 풀어볼건데, 먼저 이중 for 문으로 풀어보자.

for(int i=0; i<n; i++)
	for(int j=i; j<n; j++)
    	if(a[j]-a[i] >= m)
        	ans = min(ans, a[j]-a[i]);

매우 간단하지만 시간 복잡도가 O(N^2)이다. 하나씩 개선해보자.

 

먼저 i가 증가할수록 a[j] - a[i]가 m 이상이 되는 최초의 지점 j 또한 증가한다. 정렬된 배열이므로 당연하게 유추할 수 있다.

다음으로, 각 i에 대해 a[j] - a[i]가 m 이상이 되는 최초의 지점 j를 찾았다면 j+1, j+2, ... 는 확인할 필요가 없다. 이것도 당연하다. 이렇게 당연한 두 직관을 가지고 투 포인터 풀이로 개선할 수 있다.

 

2 3 9 13 22, M = 6인 예시로 생각해보자. 먼저 두 포인터 st, en을 arr[0] = 2에 두고 en - st >= m인 최초의 en을 찾아보자.

2(st) 3 9(en) 13 22, ans = 7이 된다. 지금 당장은 en 포인터를 뒤로 옮길 필요가 없다. 어차피 st 포인터의 값인 2에 대해서는 답이 될 수 있는 en이 존재하지 않기 때문이다. 따라서 st 포인터를 옮겨주자.

2 3(st) 9(en) 13 22 -> en - st가 6 이상이다. 따라서 min = 6이 되고 min = M 이므로 답은 이미 나왔다.

그 뒤는 더 볼 필요가 없을 것 같고 대충 2 3 9(st) 13 22(en)이 되면 en이 끝까지 왔으므로 더 볼 필요도 없이 종료하면 된다. 바로 코드로 짜보자.

/** Two Pointer 2230: 수 고르기 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;

int n, m;
long long arr[100100];
long long ans = LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr, arr + n);

    int en = 0;
    for (int st = 0; st < n; st++)
    {
        while (en < n && arr[en] - arr[st] < m)
            en++;
        // en을 찾음, en = n-1 일 때 en++을 하고 종료하므로 en == n인지 체크해야 함.
        if (en == n)
            break;
        ans = min(ans, arr[en] - arr[st]);
    }
    cout << ans << '\n';
}

사실 위에서 생각해뒀던 로직을 그대로 구현하면 돼서 어려울 부분은

        while (en < n && arr[en] - arr[st] < m)

            en++;

        // en을 찾음, en = n-1 일 때 en++을 하고 종료하므로 en == n인지 체크해야 함.

        if (en == n)

            break;

이 정도가 아닐까 싶다. 천천히 머리속으로 시뮬레이션을 돌려가면서 코드를 짜면 빼먹을 부분은 없다.

백준 1806: 부분합

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

 

수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하면 된다. 아까랑 거의 똑같은데 조건만 좀 찾아보자. st pointer는 st ~ en 까지 더해서 합이 S 이상이 되면 st는 멈추고 en을 늘리면 된다. 바로 구현해보자. 

구현은 일단 ans에 몇 자리인지를 확인해야 하고 다른 변수를 둬서 st ~ en의 합도 저장해야 한다. 

st ~ en 을 tmp에 저장한다고 하면, tmp를 구하고 en++을 하게되면 의도한 것 보다 한 칸 더 계산하게 된다. 아무튼 구현해보고 답이 틀리면 디버깅 해보면 바로 알 수 있을 것이다.

/** Two Pointer 1806 부분합 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;

int n, s;
int arr[100100];
int ans = INT_MAX;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s;

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int en = 0, tmp = arr[0];
    for (int st = 0; st < n; st++)
    {
        while (en < n && tmp < s)
        {
            en++;
            if (en != n)
                tmp += arr[en];
        }
        if (en == n)
            break;
        ans = min(ans, en - st + 1);
        tmp -= arr[st];
    }
    if (ans == INT_MAX)
        ans = 0;
    cout << ans << '\n';
}