[투 포인터] 보석 쇼핑 - 2020 카카오 인턴십

gems 배열의 크기는 최대 100000이기 때문에 O(n^2) 이상의 알고리즘으로는 효율성에서 통과하지 못할 것이다.

즉, 구간의 왼쪽과 오른쪽 끝점을 조절해가며 해답을 찾는 투 포인터 알고리즘이 필요하다.

 

해결 방식을 그림으로 표현하면 이렇다.

모든 보석의 종류를 포함하는 첫 구간(0부터 시작)을 기준으로 투 포인트 알고리즘을 수행하면 되는 방식이다.

왼쪽 끝점은 이동할 수 있는 만큼 이동하고 오른쪽 끝점은 1만큼 이동하는 과정을 반복했고, 각 과정이 끝날 때마다 구간의 길이가 최솟값이면 벡터에 저장했다.

왼쪽 끝점에 있는 보석이 구간에 단 1개만 있는 상태에서 왼쪽 끝점을 이동해버리면 그 구간은 모든 보석의 종류를 포함할 수 없게 된다. 반대로, 왼쪽 끝점에 있는 보석이 구간에 여러개가 있다면 왼쪽 끝점을 이동해도 된다는 사실을 잘 이용하면 문제를 해결할 수 있을 것이다.

 

 

소스 코드

#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct part {
    int start;
    int end;
    int length;
};

map<string, int> mcnt; // gems의 각 보석의 수를 체크
map<string, int> current_mcnt; // 구간의 각 보석의 수를 체크
int mini=100001;
vector<part> vp;

bool compare(part p1, part p2){
    if(p1.length==p2.length) return p1.start<p2.start;
    else return p1.length<p2.length;
}

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    int s=0; int e=0; // 시작점, 끝점
    
    // 보석의 종류 수 mcnt.size() 파악
    for(int i=0;i<gems.size(); i++) mcnt[gems[i]]++;

    // 모든 보석의 종류를 포함하는 첫 구간 찾기
    for(int i=0;i<gems.size();i++){
        current_mcnt[gems[i]]++;
        if(mcnt.size()==current_mcnt.size()) break;
        else e++;
    }
    if(e-s+1<=mini) vp.push_back({s, e, e-s+1});
    
    // 탐색
    while(1){
        while(s<=e){
            if(current_mcnt[gems[s]]==1) break;
            else {
                current_mcnt[gems[s]]--;
                s++;
            }
        }
        if(e-s+1<=mini) vp.push_back({s, e, e-s+1});
        if(e==gems.size()-1) break;
        e++;
        current_mcnt[gems[e]]++;
    }
    
    sort(vp.begin(), vp.end(), compare);
    answer.push_back(vp[0].start+1);
    answer.push_back(vp[0].end+1);
    return answer;
}

 

테스트케이스 15개 정확성, 효율성 만점