투 포인터 알고리즘 (백준 BOJ 2470 / Codeforces 1656B)

투 포인터(two pointer) 알고리즘은 인덱스 i, j를 나누어 arr[i]와 arr[j]에 대한 연산을 반복해서 하면서 i와 j를 조건에 따라 이동시켜가며 결과값을 찾는 알고리즘입니다.

이전에도 다룬 적이 있지만 이번에는 i와 j가 양 끝에서 시작하는 경우와 i와 j가 둘 다 인덱스 0에서 시작하는 경우 두 가지 경우로 나누어 정리해보도록 하겠습니다.

 

---

백준 BOJ 2470 : 두 용액

먼저 i는 왼쪽 끝, j는 오른쪽 끝에서 시작하여 탐색을 하는 경우입니다.

대표적인 예시로 백준 BOJ 2470번 : '두 용액' 문제가 있습니다.

 

문제에 대해 간략하게 설명하자면, N개의 값을 가진 데이터들 중에서 두 데이터의 합이 0에 가장 가깝게 되는 두 데이터를 구하는 문제입니다.

 

 

 

위와 같이 데이터들을 먼저 오름차순으로 정렬해준 뒤에, i와 j를 양단 끝으로 배치한 뒤 |sum| 값을 계속 구하면서 체크해주면 됩니다.

만약 arr[i] + arr[j] < 0이면 i를 오른쪽으로 한 칸 이동시켜 sum이 약간 더 커지게 만들어주면 되고, arr[i] + arr[j] > 0이면 j를 왼쪽으로 한 칸 이동시켜 sum이 약간 더 작아지게 만들어주는 원리입니다.

 

이 문제에서는 두 용액의 '값'을 구하라고 하였으므로 만약 sum이 0에 더 가깝다면 두 용액에 해당하는 값들을 미리 갱신시켜주었다가 탐색이 끝나면 출력해주도록 풀이 코드를 작성해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

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

    sort(arr.begin(), arr.end());

    int i = 0, j = N-1;
    int a, b, Min = INT_MAX;
    while(i < j) {
        int sum = arr[i] + arr[j];

        if(abs(sum) < Min) {
            Min = abs(sum);
            a = arr[i], b = arr[j];
        }

        if(sum == 0) break;
        else if(sum < 0) i++;
        else if(sum > 0) j--;
    }

    cout << a << " " << b;
}

 

풀이 코드는 위와 같으며, break의 조건을 sum == 0으로 두어도 됩니다.

(이는 문제에서 만약 최소값이 여러 개라면 그 중 아무거나 하나를 출력하라고 하였기 때문입니다.)

 

 

Codeforces 1656B : Subtract Operation

이 문제는 특정 규칙에 따라 주어진 수열에 대해 연산을 하고, 남은 값들이 모두 K가 되도록 만들 수 있는지의 여부를 구하는 문제입니다.

연산의 규칙은 다음과 같습니다. : 특정 원소를 선택하여 해당 원소를 제거함과 동시에 해당 원소의 값만큼을 다른 원소에서 모두 빼는 것입니다. 이를 계속 반복하여 남은 원소들이 모두 K가 될 수 있도록 만들 수 있는지를 확인하면 됩니다.

 

 

 

위와 같이 일단 원소들을 기호로 나타내어 한 번 연산을 해보면, 조금만 확인을 해봐도 특정 원소를 빼는 연산은 모든 원소에 중복되어 적용되므로 다음 연산에서 "이전에 뺀 연산이 서로 상쇄"됨을 알 수 있습니다.

그렇기 때문에 마지막으로 선택하는 두 원소의 차이가 결국 결과값이 됩니다.

따라서 차이가 K인 두 원소가 존재하기만 한다면 Yes를 출력해주면 됩니다.

 

이제 여기에서 투 포인터(two pointer) 알고리즘을 사용하여 문제를 풀이해주면 됩니다.

먼저 값들을 정렬 후, 이번에는 i와 j를 둘 다 왼쪽에서부터 출발시켜줍니다.

위의 문제에서는 두 원소의 합이 기준이었지만 이 문제에서는 두 원소의 차가 기준이기 때문입니다.

 

포인터 이동 조건은 arr[j] - arr[i] > K이면 i를 오른쪽으로 한 칸 이동시켜주고, arr[j] - arr[i] < K라면 j를 오른쪽으로 한 칸 이동시켜주면 됩니다.

종료 조건은 당연히 i가 j보다 오른쪽으로 이동해버리거나 두 포인터 중 하나 이상이 오른쪽 밖으로 도달하면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
 
    int T; cin >> T;
 
    while(T--) {
        int N, K; cin >> N >> K;
 
        vector<int> arr(N);
        for(int i=0; i<N; i++) cin >> arr[i];
        sort(arr.begin(), arr.end());
 
        int i = 0, j = 0;
 
        bool check = false;
        while(i <= j && i < arr.size() && j < arr.size()) {
            if(arr[j] - arr[i] == K) {
                check = true;
                break;
            }
            else if(arr[j] - arr[i] > K) i++;
            else if(arr[i] - arr[i] < K) j++;
        }
 
        if(check) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

구현은 위와 같이 간단하게 해줄 수 있습니다.