[문제의 접근]
두 수를 선택하고, 두수의 차이가 M이상이면서 가장 작은 차이를 구해야 한다. 어떻게 접근해야 할까? Bruteforce로 접근하면 가장 쉽게 접근법을 생각할 수 있다. 즉 모든 경우의 수를 비교해 보는 것이다. N개의 수 중에서 2개의 수를 임의로 선택해야 하기 때문에, $O(N^2)$ 시간 복잡도가 나온다. For 문을 계층적으로 2번 돌린다고 생각하면 쉽다. 첫번째 수를 정하고 N-1개 비교, 2번째 수를 정하고 N-2개 비교,.... 현재 N이 1,000이하라면 충분하겠지만, 주어진 값은 N이 100,000 으로 주어져 있다. 연산량은 $10^{10}$으로 대략적인 1초의 연산량 $10^8$을 초과하므로 시간초과다.
그럼 어떻게? $O(n\log_{2}{n})$의 접근이나, $O(n)$ 시간 복잡도를 가질 수 있는 알고리즘 적인 접근이 필요하다. 일단 주어진 수를 정렬하면 문제가 쉬워지는지 확인해 보자. 작은 순서에서 큰 순서대로 정렬해 보면 다음과 같은 편리한 점이 있다는 것을 깨닫게 된다. 바로 일정 부분을 탐색하고 나면 그 이후는 탐색할 필요가 없다는 사실이다. 왜냐하면 최소값을 찾는 문제이고, M이상만 확보하게 되면 그 이상은 더 탐색해 볼 필요가 없기 때문이다.
[1,3,5,7,8,9,11,15] // M=2라면 1과 3을 비교하고 나면 그 이후로는 비교할 필요가 없어진다. 수가 더 커지니까.[Two-pointer]
이것을 응용한 방법이 바로 Two-pointer이다. Two-pointer는 어렵게 생각할 필요없이, 2개의 포인터를 사용한다고 생각하면 쉽다. 2개의 포인터의 위치를 이동시켜가면서 원하는 정답을 이끌어 낸다고 보면 된다. 상황에 따라서 포인터의 위치 조정이 필요하지만, 위와 같은 문제에서는 리스트의 시작점에서 시작한다. 아래의 그림을 보면 이해가 쉬울 것 같다. 두 포인터가 시작위치에서 시작하고 M이 5라고 시작해 보자. 편의상 왼쪽 포인터를 L, 오른쪽 포인터를 R로 지칭한다면 두 값의 차이가 5 이상이 될 때까지는 R포인터를 계속 큰 값쪽으로 이동시킨다. 그리고 5이상을 만족하면 그 때의 차이값을 저장해 두고 이번에는 차이가 줄어들수 있는지 확인하기 위해 L포인터를 이동시킨다. 마찬가지로 L 포인터도 5이상을 만족하면 계속 이동 시킨다. 이런 방식을 리스트가 끝날때까지 진행하면서 해를 구하는 식이다.
[Two-pointer 시간 복잡도]
그렇다면 Two-pointer의 시간 복잡도는 얼마일까?, 리스트를 순회하는 포인터가 2개이고 한번 오른쪽으로 움직이면 왼쪽으로 돌아오지 않기 때문에 시간 복잡도는 $O(2*N) = O(N)$ 이 된다. 솔찍히 $O(N)$ 복잡도의 알고리즘 풀이는 쉽게 나오지 않고, stack 이용 및 이렇게 sliding window 방식으로 해를 구할 때 처럼 그 경우가 많지 않아서, 문제의 유형에 익숙해 지는 편이 좋다.
[Two-pointer 구현]
구현 자체는 말로 설명한 것과 같이 simple한 구조를 가지고 있으며 보통 while문을 돌려서 구하고, 리스트의 끝에 도달하는 조건으로 종료 조건을 설정한다. Python과 C++모두 구현에 큰 차이가 없다.
<C++>
int check(int* arr) {
int sol = inf;
int l = 0; // left pointer
int r = 0; // right pointer
//어느 한 pointer가 리스트에 끝에 도달할 때까지 진행
while ((l < n) && (r < n)) {
if (arr[r] - arr[l] < m) r += 1; // 두 값의 차가 m보다 작으면 right pointer 증가
else { // 그렇지 않으면 솔루션 저장하고 left pointer 증가
sol = min(sol, arr[r]-arr[l]);
l += 1;
}
}
return sol;
}<Python>
def check():
sol = inf
l, r = 0, 0
while l < n and r < n:
if (arr[r] - arr[l]) < m:
r += 1
else:
sol = min(sol, arr[r]-arr[l])
l += 1
return sol[전체 솔루션]
위의 check 함수의 return 값을 받아서 그대로 출력하면 풀이는 종료된다. 전체 풀이는 아래 링크를 참조하는 게 좋다.
Python https://github.com/Koo82/Algotirhm/blob/main/%5BBS%5DBJ_2230.py
C++ https://github.com/Koo82/Algotirhm/blob/main/%5BBS%5DBJ_2230.cpp
'알고리즘 > Two Pointer' 카테고리의 다른 글
| [Binary Search && Two pointer]BJ_3151, 합이 0 (0) | 2023.03.23 |
|---|
