[프로그래머스] [카카오 인턴]보석 쇼핑

프로그래머스의 Lv.3 [카카오 인턴]보석쇼핑입니다.

문제 출처

[카카오 인턴]보석 쇼핑

문제 해설

우선 문제의 조건을 보자.
gems 배열의 크기는 1 이상 100,000 이하입니다.
이 조건을 봤을 때, 시간복잡도가 n^2를 넘어간다면, 연산 수는 100,000,000,000으로 절대로 시간 내에 풀 수 없다. 그렇기 때문에 시간 복잡도를 가능한 nlogn 이하로 내려야 한다. 이 점을 생각하면서 문제를 풀어보자.

결국 문제는 모든 종류의 보석을 적어도 1개 이상 포함하는 연속되면서 가장 짧은 구간을 구하는 것이다.

내가 생각한 해결 방법은

1. gems에 어떤 보석들이 있는지 구하기 위해서, HashSet을 생성해서, gems를 순회하면 HashSet에 넣는다.
2. <string, int>를 가지는 HashMap을 생성한다. String은 gems의 이름, int는 현재 HashMap에 들어가 있는 gems의 개수이다.
   1. gems를 처음부터 돌면서, HashMap에 값이 없다면, HashMap에 값을 넣는다.
      1. HashMap의 크기가 HashSet의 크기와 같다면, 현재 문제가 요구하는 조건을 찾은 것이다. 이를 결과 벡터에 저장한다.
      2. HashMap의 처음 부분부터 인덱스를 증가시켜가며, HashMap에서 해당 값들을 하나씩 지운다.
      3. HashMap의 int 값이 0이 되면 해당 key값을 HashMap에서 삭제한다. 이후 break한다.
      4. HashMap의 크기가 HashSet의 크기보다 작아지면, 문제가 요구하는 조건을 만족하지 않음으로 다시 gems를 돌기 시작한다.
      5. 작이지기 전까지는 항상 조건을 만족함으로 결과 벡터에 저장한다.
   2. gems의 끝에 도달하면 반복문을 break한다.
3. 결과들은 결과 벡터에 저장되어 있음으로, 결과 벡터에서 가장 범위가 작은 값을 return 한다.

이렇게 풀면 최대 O(N)안에 문제를 해결 할 수 있다.

#include <bits/stdc++.h>

using namespace std;

unordered_set<string> h_Set;
unordered_map<string, int> h_Map;

vector<int> solution(vector<string> gems) {
    vector<vector<int>> answer;
    
    for(auto a : gems)
        h_Set.insert(a);
    int MaxNum = h_Set.size();

    int aP = 0; int bP = 0;
    for(int i=0;i<gems.size();++i){
        ++bP;
        h_Map[gems[i]]++;
        if(h_Map.size() == MaxNum){
            while(true){
                if(h_Map[gems[aP]] == 1){
                    h_Map.erase(gems[aP]);
                    vector<int> temp;
                    temp.push_back(++aP);
                    temp.push_back(bP);
                    answer.push_back(temp);
                    break;
                }else{
                    h_Map[gems[aP]]--;
                    ++aP;
                }
            }
        }
    }
    
    int answerCount = 1000000;
    int answerCheck = -1;
    for(int i=0;i<answer.size();++i){
        int temp = answer[i][1] - answer[i][0];
        if(answerCount > temp){
            answerCount = temp;
            answerCheck = i;
        }
    }
    
    return answer[answerCheck];
}