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

프로그래머스

 

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

// 진열된 모든 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
// 투 포인터 알고리즘

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    unordered_map<string, int> um;
    
    for(int i = 0; i < gems.size(); i++)
        um[gems[i]] = 0;
    
    int start = 0, curGem = 0;
    answer.push_back(0);
    answer.push_back(100001);
    
    for(int end = 0; (end < gems.size()) && start <= end;) {
        // start와 같은 보석이 나오거나 start 지점의 보석과 같은 보석을 여러번 집었다면
        if((end != start && gems[start] == gems[end]) || um[gems[start]] > 1) {
            if(!(--um[gems[start++]])) curGem--;
            continue;
        }
        // end 지점의 보석을 처음 주워본다면
        else if(um[gems[end]]++ == 0) {
            curGem++;
        } 
        
        // 모든 종류의 보석을 집었을 때
        if(curGem == um.size()) {
            // 구간의 길이가 더 짧다면
            if(answer[1] - answer[0] > end - start) {
                answer[0] = start + 1;
                answer[1] = end + 1;
            }
            
            // 해당 구간에서 시작 지점 빼주기
            if(!(--um[gems[start++]])) curGem--;
        }
        
        end++;
    }
    
    return answer;
}