(프로그래머스 c++ KAKAO)보석 쇼핑

큐와 맵을 이용하여 문제를 푼다.

 

우선 string을 담을 수 있는 큐인 q와 map<string, int> m을 선언한다.

그리고 보석 종류의 개수를 구하기 위한 gems_size, 진열대 시작 번호 start, 진열대 마지막 번호 end, 시작 지점 바꿔주기 위한 tmp를 0으로 초기화한다.

 

이제 보석 종류의 개수를 구하도록 한다.

for문을 통해 gems를 순회하면서 m에 넣어주도록 한다.

gems_size = m.size()로 하여 개수를 저장하고, m은 clear하여 비워주도록 한다.

 

다시 gems를 순회하면서 정답을 알아내면 된다.

m을 초기화 하였으니 m[gems[i]] == 0이면 1을 넣어주고,

0이 아니라면 같은 보석이 이미 있는 경우이므로 해당 보석의 개수를 +1로 해준다.

그리고 q에 push.

 

모든 종류의 보석은 1개 이상 가지고 있어야 한다.

m.size()가 gems_size와 같을 때까지 q에 push하고, q.front()가 1개 이하가 되지 않을 때까지 pop을 한다.

 

1개 이하가 되지 않도록 while문으로 보석의 개수를 검사한다. 

만약 q.front()에 있는 보석의 개수가 2개 이상이라면 해당 보석의 개수를 -1 해주고, pop()을 해준다.

그리고 tmp++을 시켜주어 시작 포인트를 갱신시켜준다.

만약 q.front()의 개수가 1이라면 break.

 

마지막으로 m.size()가 gems_size와 같고, end > q.size()면 start와 end를 갱신시켜준다.

 

for문이 끝났으면 answer[0] = start + 1, answer[1] = start + end를 해주어 정답을 넣어주면 끝..!

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer = {0, 0};
    queue<string> q;
    map<string, int> m;
    int gems_size = 0, start = 0, end = 1000001, tmp = 0;
    
    for(auto i : gems)
        m[i] = 1;
    
    gems_size = m.size();
    m.clear();
    
    for(int i = 0; i < gems.size(); i++)
    {
        if(m[gems[i]] == 0)
            m[gems[i]] = 1;
        else
            m[gems[i]] += 1;
        q.push(gems[i]);
        
        while(1)
        {
            if(m[q.front()] > 1)
            {
                m[q.front()] -= 1;
                q.pop();
                tmp++;
            }
            else
                break;
        }
        
        if(m.size() == gems_size && end > q.size())
        {
            end = q.size();
            start = tmp;
        }
    }

    answer[0] = start + 1;
    answer[1] = start + end;
    return answer;
}