프로그래머스 - 보석 쇼핑(67258)

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

프로그래머스

---

문제 설명

진열장에 보석명 순서대로 들어있습니다. 본인은 배열의 특정 범위의 보석을 모두 구매하되 아래 목적을 달성하고 싶습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
예를들어 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE)이 8개가 진열된 진열대입니다.
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
위 진열대는 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 1개 이상씩 포함하게 됩니다.
3,4,6,7번의 보석만 구매하는 것은 5번이 빠지게 되어 연속되지 못해 해당되지 않습니다.

다음 진열대들에서 가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 담아서 return하며, 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

제한조건

gems 진열대 배열의 크기 : 1 ~ 100,000 
진열대 배열의 원소 : 1~10 길이의 알파벳 대문자로만 구성된 문자열

---

아이디어

1. 먼저 보석의 종류를 모두 확인한다. O(N)
2. 연속된 구간이니 투포인터로 구간을 아래와 같이 훑습니다. O(N) + 구간 체크에 O(logN)
2-1 : 훑은 구간에 보석이 모두 포함되지 않으면 e를 이동시키며 구간을 확장시킨다.
2-2 : 훑은 구간에 보석이 모두 포함되면 길이를 기록하고 s를 앞으로 이동시켜 구간을 줄인다.
2-3 : e가 끝에 도달하면 s를 당기면서 기록한다.

---

코드

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer = {0, (int)gems.size()};
    unordered_set<string> sset;
    
    //1 보석 종류 체크
    for(auto gem : gems){
        sset.insert(gem);
    }
    
    int s = 0, e = -1;
    unordered_map<string, int> check;
    
    //2
    while(s < gems.size()){
    	//2-3
        if(e == gems.size()-1){
            if(check.size() == sset.size())
            {
                if(answer[1] - answer[0] > e - s)
                {
                    answer[0] = s;
                    answer[1] = e;
                }
            }
            check[gems[s]] -= 1;
            if(check[gems[s]] == 0){
                check.erase(gems[s]);
            }
            s++;
        }
        else{
        	//2-1
            if(check.size() == sset.size()){
                if(answer[1] - answer[0] > e - s)
                    {
                        answer[0] = s;
                        answer[1] = e;
                    }
                check[gems[s]] -= 1;
                if(check[gems[s]] == 0){
                    check.erase(gems[s]);
                }
                s++;
            }
            //2-2
            else{
                e++;
                if(check.find(gems[e]) == check.end())
                {
                    check.insert(make_pair(gems[e], 1));
                }else{
                    check[gems[e]] += 1;
                }
            }
        }
    }
    
    answer[0] += 1;
    answer[1] += 1;
    
    return answer;
}

---

○ 보석 확인을 위해 hash 구조인 unordered_map으로 내가 가지고 있는 보석 종류(key 개수)와 해당 보석 개수(int)로 정리

○ 실질적으로 hash구조이니 O(1)로 체크가 가능하다면 O(N)으로 해결 가능..?