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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

 

 

풀이

모든 종류의 보석을 담아야하므로 모든 종류의 보석을 알아야한다.

따라서, set을 통해 보석을 모두 담으면 중복이 제거되어 모든 보석 종류가 들어가있다.

 

다음은 투 포인터 알고리즘을 이용하여 start pointer부터 end pointer까지의 보석이 모든 보석 종류를 담고있는지 확인해야한다. 이를 위해 보석의 이름을 key값으로 가지고 개수를 value값으로 가지는 unordered_map을 선언한다.

 

이 map은 처음에는 비어있으므로 set의 사이즈와 같아지면 모든 보석의 종류를 담고 있다고 할 수 있다.

만약 같지 않다면 end pointer를 계속 늘려가며 보석 이름에 맞는 value 값을 증가시켜준다.

 

같아지면 end pointer의 위치가 고정된 것이다. 이제 start pointer를 늘려가며 보석의 개수를 줄여나가고 만약 보석의 개수가 1이라면  start pointer도 고정시켜준다. 이 때, erase 시켜주는 이유는 value를 0으로 만들면 보석이 없는데 map의 크기는 그대로이기 때문에 아예 삭제하여 map의 크기도 줄이기 위해서이다.

 

두 포인터를 고정하였으므로 최소 길이보다 작다면 정답을 갱신시켜준다.

 

가운데에

else if(en == gems.size()) break;

가 있는 이유는 테스트 케이스 4번과 같이 end pointer가 끝까지 가야 모든 보석을 포함하는 경우가 있기 때문이다.

gems의 크기가 3일 때 end pointer가 3까지 간다면 gems[3]은 범위를 초과하여 접근하기 때문에
해당 구문이 없다면 오류가 발생한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer(2);
    set<string> s;
    
    for(int i=0; i<gems.size(); i++){
        s.insert(gems[i]);
    }
    
    int st = 0, en = 0, len = 1e9;
    unordered_map<string, int> m;
    
    while(en <= gems.size()){
        if(m.size() == s.size()) {
            if(m[gems[st]] == 1) m.erase(gems[st++]);
            else m[gems[st++]]--;
            
            if(en - st < len){
                len = en - st;
                answer[0] = st;
                answer[1] = en;
            }
        }
        else if(en == gems.size()) break;
        else m[gems[en++]]++;
    }
    
    
    return answer;
}