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

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/67258

풀이

---

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾기 위해 주어진 배열을 순서대로 map에 넣고, 모든 보석의 개수가 1개 이상인 경우 해당 구간의 길이를 저장한다. 추가적으로 모든 보석의 개수가 1개 이상인 경우가 발생할 경우, 기존 저장한 구간의 길이와 비교하여 더 짧은 것을 저장한다.

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

using namespace std;

vector<int> solution(vector<string> gems) 
{
    vector<int> answer;
    unordered_map<string, int> displayType;
    for (int i = 0; i < gems.size(); i++)
    {
        if (!(displayType.find(gems[i]) != displayType.end()))
        {
            displayType.insert({ gems[i],1 });
        }
    
        else displayType[gems[i]]++;
    }
 
    int min = gems.size();

    unordered_map<string, int> shopCnt;
    int start_idx = 0;
    for (int i = 0; i < gems.size(); i++)
    {
        shopCnt[gems[i]]++;

        if (shopCnt.size() == displayType.size())
        {
            while (shopCnt[gems[start_idx]] > 1)
            {
                shopCnt[gems[start_idx]]--;
                start_idx++;
            }

            if (i - start_idx < min)
            {
                min = i - start_idx;
                answer = { start_idx + 1, i + 1 };
            }
        }
    }

    return answer;
}