Programmers : 보석 쇼핑

풀이요약

투 포인터 + 맵

풀이상세

1. 중복을 제거한 경우 나타나는 총 갯수, 즉 모든 종류의 보석을 산 하나씩 구매한 경우를 구한다. 한번의 반복문을 통해 Set 의 사이즈를 찾으면 알 수 있다.

2. Map 을 통해 사이즈를 증가시키며, Set() 의 경우 만큼 찰 때 까지 계산한다. Set() 의 사이즈에 도달한 경우, 중복된 값이 존재하는 지를 확인하며 이를 빼준다.

3. 이 과정을 반복했을 때 범위가 가장 적은 경우를 찾으면 된다.

#include <string>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;
int l, r, len, cnt = 987654321;
unordered_map<string, int> m;
set<string> s;

vector<int> go(vector<string> &gems) {
    for(string g : gems) s.insert(g);
    vector<int> ans;
    while(r < gems.size()) {
        m[gems[r]]++;
        if(m.size() == s.size()) {
            while(m[gems[l]] > 1) {
                m[gems[l++]]--;
            }
            
            if(cnt > (r-l)+1) {
                cnt = (r-l)+1;
                ans = {l+1, r+1};
            }
        }
        r++;
    }
    return ans;
}
vector<int> solution(vector<string> gems) {
    return go(gems);
}