프로그래머스 Level 3 보석 쇼핑[C++]

1. 문제 풀이

 문제 유형은 투 포인터입니다. 보석 종류가 문자열로 주어지기 때문에 해시를 사용하여 보석 종류마다 숫자를 부여해 줍니다. 투 포인터를 사용하여 모든 보석을 포함하는 구간을 찾아 그 구간의 길이가 최소가 될 경우 갱신해 주는 방법을 사용했습니다. 투 포인터를 알고 있다면 무난하게 풀 수 있을 것 같습니다.

 

2. 코드

#include <bits/stdc++.h>

using namespace std;

int mx;
unordered_map<string, int> idx;

vector<int> solution(vector<string> G) {
    for(auto x : G) {
        if(idx.find(x) == idx.end()) {
            idx[x] = mx++;
        }
    }

    int ansx{0}, ansy{100'000};
    int cnt{}, en{};
    vector<int> chk(mx);
    for(int st = 0; st < G.size(); st++) {
        while(en < G.size() && cnt < mx) {
            if(!chk[idx[G[en]]]) cnt++;
            chk[idx[G[en]]]++;
            en++;
        }

        if(cnt == mx && ansy - ansx > en - st) {
            ansx = st;
            ansy = en;
        }

        chk[idx[G[st]]]--;
        if(!chk[idx[G[st]]]) cnt--;
    }

    return {ansx+1, ansy};
}