프로그래머스 문제 - 보석 쇼핑

프로그래머스 보석 쇼핑 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

진열된 보석들의 이름들을 순서대로 나열한 배열이 주어집니다.
지정된 위치부터 순서대로 모든 종류의 보석을 구매할 때까지 전부 보석을 구매힙니다.
중복된 보석을 사더라도 모든 종류의 보석을 구매할 때까지 계속해서 구매합니다.
지정된 위치부터 모든 종류의 보석을 구매한 지점이 한 구간이라고 생각하였을 때 제일 짧은 구간을 구해야합니다.

문제 풀이

보석의 종류가 몇가지인지 알기 위해 set을 사용해줍니다.

set<string> s;
    
 //보석의 종류가 몇가지인지 검색
for(string str : gems)
{
    s.insert(str);
}

빠른 검색을 위한 unordered_map과 현재 가져간 보석들을 저장하기 위한 queue를 선언해줍니다.

주어진 배열의 앞에서부터 하나씩 unordered_map에 넣어주며 현재까지 구매한 보석들의 종류를 저장해주고, 구매한 보석은 순서대로 queue배열에 저장해줍니다.

만약 보석들을 구매하던 도중 queue배열의 제일 앞에 있는 보석을 2개 이상 구매하였을 경우 제일 앞에 있는 보석을 빼더라도 이후 구간에 그 보석이 존재한다는 뜻이므로 queue배열의 앞부분을 pop해줌과 동시에 시작지점을 하나씩 뒤로 가주며 최소한의 구간을 만들어주면 됩니다.

이후 unordered_map과 이전에 구한 set의 size가 같으면 모든 보석들의 종류를 전부 구매했다는 뜻이므로 보석을 가져간 시작지점과 현재까지 가져간 지점이 한 구간이 됩니다.
이 구간들 중 제일 작은 구간을 return하면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    set<string> s;
    unordered_map<string, int> gemIndex;
    
    //보석의 종류가 몇가지인지 검색
    for(string str : gems)
    {
        s.insert(str);
    }
    
    int gemSize = s.size();
    answer.push_back(1);
    answer.push_back(100001);
    queue<string> q;
    int start = 0;
    for(int i = 0; i < gems.size(); i++)
    {
        //이미 구매했던 보석일 경우 갯수를 더해줌
        auto iter = gemIndex.find(gems[i]);
        if(iter != gemIndex.end())
        {
            iter->second++;
        }else
        {
            //구매했던 보석이 아닐 경우 map에 추가
            gemIndex.emplace(make_pair(gems[i], 1));
        }
        //구매한 보석들을 순서대로 push해줌
        q.push(gems[i]);
        
        //만약 제일 앞의 보석을 2가지 이상 구매했을 경우 앞에 있는 보석을 하나씩 빼줌
        while(true)
        {
            if(gemIndex.find(q.front())->second > 1)
            {
                gemIndex.find(q.front())->second--;
                q.pop();
                //앞에서 하나씩 보석을 뺐으므로 시작지점도 이동해줌
                start++;
            }else
            {
                break;
            }
        }
        
        //만약 보석의 모든 종류를 구매했을 경우
        if(gemIndex.size() == gemSize)
        {
            if(answer[1]-answer[0] > i-start)
            {
                answer[0] = start;
                answer[1] = i;
            }
        }
    }
    answer[0]++;
    answer[1]++;
    return answer;
}

출저

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