SMParkWorld - [C/C++] Two Pointer 투 포인터

[C/C++] Two Pointer 투 포인터

2021-06-15 13:01:27

Algorithm

오늘은 투 포인터에 대해서 적어두려 한다.

투 포인터는 이름의 뜻과 동일하게 두개의 포인터를 사용해서 문제를 풀이하는 방법이다. 여기서의 포인터는 * 구두점을 사용한 포인터 변수를 사용하는 방법도 있겠지만 주로 두 개의 Index를 사용한다고 이해하면 편할 것 같다.

투 포인터 알고리즘을 활용할 수 있는 곳은 대부분 빠른 시간 안에 문제를 풀어야할 때 사용된다. 예를 들어 1차원 배열이 주어지고 이 배열의 일정 구간 합이 임의의 수보다 높은 구간을 탐색하는 문제다. 아주 간단하게 생각한다면 2중 반복문을 사용해서 완전 탐색을 통해 풀어낼 수 있다. 하지만 이 경우는 시간복잡도가 O(n²)이 되므로 길이가 대략 100,000 이상의 배열이 주어지게 되면 효율성 테스트에서 시간초과 0점을 맞게 될 것이다. 하지만 이 문제를 시간복잡도 O(n)으로 풀어내는 방법이 바로 투 포인터다.

투 포인터의 알고리즘을 사용해서 1차원 배열에서 일정 구간 합이 임의의 수보다 높은 구간 중 가장 짧은 구간을 탐색하는 방법은 아래와 같다.

start Index와 end Index를 맨 앞에 위치한다.
end Index를 한칸씩 늘려가며 end Index의 배열 값을 누적으로 저장하고 이 누적값이 임의의 숫자보다 높은지 확인한다.
end Index를 늘리던 중 누적값이 임의의 숫자보다 높아진 경우 start Index의 배열 값을 누적값에서 빼고 start Index를 한칸 늘린다.
3번의 결과 값이 임의의 숫자보다 높은 경우 3번을 반복하고 임의의 숫자보다 낮은 경우 end Index와 start Index의 차이를 비교 후 저장하고 2번부터 반복한다.
end Index가 배열의 끝까지 이동했을 경우 탐색을 종료한다.

위와 같이 탐색한다면 start Index에서 배열 순회 1번 end Index에서 배열 순회 1번, 총 2n번 조회를 수행함으로 시간복잡도 O(n)을 갖는 알고리즘이다. 아래는 최근 풀었던 알고리즘 문제 중 투 포인터 알고리즘을 활용했던 문제를 가져왔다. 이 문제는 카카오 인턴십의 보석 쇼핑 문제고 프로그래머스에서 풀 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    set<string> target(gems.begin(), gems.end());
    
    int start = 0;
    map<string, int> basket;
    for (int end = 0; end < gems.size(); end++) {
        basket[gems[end]]++;
        if (basket.size() == target.size()) {
            do {
                if (--basket[gems[start]] == 0) {
                    basket.erase(gems[start]);
                    if (answer.size() == 0 || answer[1] - answer[0] > end - start) {
                        answer.clear();
                        answer.push_back(start + 1);
                        answer.push_back(end + 1);
                    }
                    start++;
                    break;
                }
            } while (++start <= end);
        }
    }
    return answer;
}