투 포인터란?
투 포인터란 배열에서 원래 이중 for문으로 O(N2)에 처리되는 작업을 2개 포인터의 움직으로 0(N)에 해결하는 알고리즘
그렇다면 투 포인터가 어떤 원리로 작동하기에 시간복잡도를 그렇게 줄일 수 있냐고 묻게 된다면 이렇게 말할 수 있다.
이중 for문에서 i = 0 일때 j 가 0부터 n -1 까지 돌고, 이처럼 i 가 n -1 일때까지 각각 인덱스는 i = 0, i = 1, i =... 일때까지 계산되어진 데이터를 전혀 쓰지않는다. 하지만 투 포인터를 이용한다면, i = 0일때 계산하면서 얻은 정보를 i = 1일때 활용하게된다. 그 전까지 계산된 값의 정보가 포인터의 이동으로 나타나는 것이다.
그래서 이전에 풀이하였던, 이분 탐색으로 투 포인터 문제를 풀 수 있는 경우가 있다. 반대로 이분탐색 문제들을 투 포인터를 이용하여 해결할 수 있는 경우도 많다고 한다.
다음은 백준 2230번 문제를 풀면서 자세히 알아보자.
먼저, 이분탐색과 비슷한 방향으로 시작한다. st는 이중 for문의 i 인덱스와 같은 역할을, en은 j 인덱스와 같은 역할을 한다고 생각하자. min은 값의 최소값을 저장할 변수인데 일단 infinity로 최대값으로 초기화한다.
각 st에 대하여 a[st] - a[en]이 m 이상이 되는 최초의 en의 값을 찾는다. 처음에 생각할것은 a[en] - a[st] > m 되는 지점을 찾아 en + 1 씩 증가하면서 값을 찾는 것이다. M = 6으로 설정되었기 때문에 적어도, en = 2가 되는 순간 min을 7로 저장한다.
이 이상으로, en을 증가시켜두어도 min이 7 이상으로 커지기 떄문에 그만해도 된다.
이 다음은, st를 증가시켜 min = 6 이상일떄를 찾아야하는데, 신기하게도 st = 1일때, en = 2에 포인터가 지정하기 떄문에, 바로 min을 갱신시키면 된다. st =1에서 이미 해야할걸 끝냈기 때문에, st + 1을 오른쪽 한칸으로 옮기려고 한 순간, a[en] - a[st] < m 이기 떄문에 다시 en을 옮길 차례이다.
이러한 방식으로, 계속 min을 갱신하기 위한 작업을 반복하게 된다면, 각 st에 대해 모든 en을 확인하는것이 아닌 이전의 en 값을 계속 가지고 있따가 효율적으로 써먹는 투 포인터를 활용하게 된다. en과 st이 각각 한칸 움직이고 끝나니까 st와 en이 움직이는 최대 거리는 2N이 된다. 이러한 방식으로 결국 시간 복잡도는 O(N)을 수행하기 떄문에 시간복잡도를 최대한 활용할 수 있게 된다.
이를 코드로 재작성해본다.
#include <iostream>
#include <algorithm>
#include <limits.h> // Max, Min
using namespace std;
int n, m;
int a[100000];
int mini = INT_MAX;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n);
int en = 0;
for (int st = 0; st < n; st++)
{
while (en < n && a[en] - a[st] < m) en++;
if (en == n) break; //en이 n을 벗어남.
mini = min(mini, a[en] - a[st]);
}
cout << mini;
}
