Level 3. 보석 쇼핑

Level 3. 보석 쇼핑

 

 

투 포인터 문제였다.

 

첫 시도에서 앞에서부터가 아니라 뒤에서부터 진행시켜서 조금 헷갈렸었다.

 

해시 테이블을 통해 보석 종류와 개수를 저장하고, 모든 보석이 포함된 경우 앞에서부터 1개씩 빼주면 된다.

• 그리고 최소 길이를 별도로 관리해 더 짧은 경우 정답을 갱신해주면 된다.

 

최소 길이를 변수로 관리할 생각도 못했어서 좀 헷갈렸었는데, 변수를 잘 활용하는 습관을 들이자.

 

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

using namespace std;

vector<int> solution(vector<string> gems)
{
    vector<int> answer;
    unordered_map<string, int> umap, current;
    size_t n = gems.size();
    int minLen = n;

    for (string& gem : gems)
        ++umap[gem];

    for (int s = 0, e = 0; e < n; ++e)
    {
        ++current[gems[e]];

        if (current.size() == umap.size())
        {
            while (2 <= current[gems[s]])
                --current[gems[s++]];

            int len = e - s;

            if (len < minLen)
            {
                minLen = len;
                answer = {s + 1, e + 1};
            }
        }
    }

    return answer;
}