프로그래머스 - 보석 쇼핑

프로그래머스 - 보석 쇼핑

map을 사용하는 sliding window 문제이다.

left와 right를 두고, 조건에 맞춰서 1씩 증가시키면서 문제에서 요구하는 조건을 만족할 때마다 정답을 업데이트해주면 된다.

문제에서 원하는 것은 인풋으로 주어지는 gems의 배열이 있고, 해당 배열에 존재하는 모든 종류의 원소를 다 포함하고 있는 가장 짧은 특정 범위를 찾는 것이다. (만약 그것이 여러개라면 시작 지점이 가장 작은 것)

이를 풀기 위해 먼저 left와 right를 0으로 두고, map<string, int> m의 형태로 맵을 관리한다.
본 문제에선 해당 맵을 m[보석] = 등장 빈도 수 로 관리할 것이다.

그 후 right를 1씩 증가시키면서 map에 존재한다면 value 값을 1씩 증가시켜주고, 없다면 map에 insert해준다.
map의 크기가 보석의 종류의 수와 같아질 때 까지 right를 증가시켜주면 된다.
만약 map의 size가 보석의 종류의 수와 같다면 left를 증가시켜서 다음 window를 sliding 시켜준다.
이 때, map[gems[left]]에 해당하는 value 값을 1줄여줘야 한다. (윈도우가 움직였기 때문에 gems[left]는 더 이상 현재 윈도우에 존재하지 않음)
또한 map[gems[left]] 값이 0이 된다면, 현재 윈도우에 존재하는 보석의 종류의 수가 줄어드는 것이기 때문에 map에서 완전히 erase해줘야 한다.

위 과정을 겪은 뒤 만약 map의 크기가 바뀌었다면 right값을 증가시켜서 윈도우 크기를 증가시켜준다. 만약 map의 크기가 바뀌지 않았다면, left를 더 증가시킬 수 있는 가능성이 존재하는 것이기 때문에 right를 증가시켜주면 안된다.
단, 다음 iteration에서 map[gems[right]]가 존재할 것이기 때문에 gems[right]가 마치 또 등장하는 것처럼 취급될 수 있다. 이를 방지해주기 위해서 map[gems[right]]의 value 값을 1 감소시켜준다. (코드의 39~40번째 Line)

코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer(2, 0);
    
    map<string, int> m;
    for(int i=0;i<gems.size();i++) 
        m[gems[i]] = 1;
    int type = m.size();
    
    m.clear();
    int min_range = 1 << 20;
    int left = 0, right = 0;
    while(1) {
        if(left > gems.size() - 1 || right > gems.size() - 1)
            break;

        if(m.find(gems[right]) == m.end()) 
            m.insert( { gems[right], 1 } );
        else 
            m[gems[right]]++;
        
        if(m.size() == type) {
            int range = right - left + 1;
            if(range < min_range) {
                answer[0] = left + 1;
                answer[1] = right + 1;
                min_range = range;
            }
            m[gems[left]]--;
            if(m[gems[left]] == 0)
                m.erase(gems[left]);
    
            left++;
            if(m.size() != type) right++;
            else m[gems[right]]--;
        } else 
            right++;
    }
    return answer;
}