보석 쇼핑

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

프로그래머스

 

set<string> st로 전체 보석의 수를 구한다.

투포인터 left, right로 보석의 범위를 제한하고 map<string, int> mp로 현재 범위의 보석을 세준다.

 

mp의 크기와 st의 크기가 같은경우는 모든 보석이 범위에 포함되어있는 경우.

범위의 크기가 이전보다 작다면 갱신, 아니라면 갱신하지 않는다.

 

left를 1씩 늘려 범위를 줄여나가면서 범위의 보석의 종류가 전체 보석의 종류보다 작다면, 다시 right를 1씩 늘린다.

 

A, A, B, C, C 라면,

A, A, B, C 까지 while문이 돌고, left가 1 늘어 A, B, C로 갱신된다는 뜻.

right가 전체범위를 벗어나면 위와 같은 방법으로 진행하고 break로 탈출한다.

 

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

using namespace std;

vector<int> solution(vector<string> gems)
{
    vector<int> answer = {0, 0};
    set<string> st;
    map<string, int> mp;
    for (string s : gems)
    {
        st.insert(s);
    }
    int count = st.size();

    int left = 0;
    int right = 0;
    int size = gems.size();
    int minimum = 1e9;

    while(true)
    {
        if (left > right) break;
        if (right >= size)
        {
            while (true)
            {
                if (mp.size() == count)
                {
                    if (minimum > right - left)
                    {
                        answer[0] = left;
                        answer[1] = right;
                        minimum = right - left;
                    }
                    mp[gems[left]]--;
                    if (mp[gems[left]] == 0)
                    {
                        mp.erase(gems[left]);
                    }
                    left++;
                }
                else
                {
                    break;
                }
            }
            break;
        }

        if (mp.size() == count) //모든 보석 추가됨
        {
            if (minimum > right - left)
            {
                answer[0] = left;
                answer[1] = right;
                minimum = right - left;
            }

            mp[gems[left]]--;
            if (mp[gems[left]] == 0)
            {
                mp.erase(gems[left]);
            }
            left++;
        }
        else
        {
            mp[gems[right++]]++;
        }
    }

    answer[0]++;
    return answer;
}