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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

분류 : 맵, 이분 탐색

---

문제 풀이는 다음과 같다.

1. map을 활용하여 보석의 이름과 보석의 갯수를 저장한다. 이때 보석의 갯수는 초기화 값인 '0'이다.

이를 통해 우리는 보석의 이름을 중복없이 저장하여 보석의 총 합 갯수를 파악할 수 있다.

2. 이분 탐색을 실시한다. 이분탐색의 과정은 다음과 같다.아래 코드에 적힌 번호를 보며 아래 해설을 참고하자.

  <보석의 갯수를 다 채웠을 경우>

  (1) 아래 코드의 1번의 경우, 모든 보석들을 1개 이상씨 갖고 있을때, 현재의 범위를 파악하여 기존에 저장된 범위보다 작은 값의 범위일 경우 저장을 해준다. 

  (2) 시작 지점의 보석을 1개 보다 많이 갖고 있는 경우, 시작 지점을 +1 증가시키고 시작지점이 변경된것을 반영하여 해당 보석의 갯수를 감소시킨다. 이때 cnt의 갯수는 감소되지 않는데, 이유는 여전히 해당 보석의 갯수가 1개 이상이기 때문이다.

  (3) 시작 지점의 보석을 1개 이하(보석의 갯수를 다 채웠으니, 결국 1개인 경우밖에 해당되지 않음)인 경우, 시작 지점을 +1 증가시키고 시작지점이 변경 된 점을 반영하여 해당 보석의 갯수를 -1 해준다. 또한, 1개였던 보석을 0개로 되돌렸으니 전체 cnt의 갯수를 -1 감소시킨다.

  (4) 만약 end 지점이 보석의 사이즈와 동일할 경우, 모든 영역을 둘러보았다는 의미이므로 while문을 빠져나온다.

<보석의 갯수를 못채웠을 경우>

  (5) end 지점에 있는 보석의 갯수가 0인 경우, cnt를 +1 증가시킨다. 이 말은 즉슨, 해당 보석이 이제 곧 +1개 추가될 것이므로, 필요한 보석의 갯수 중 1개를 충족했음을 의미한다.

 (5-2) end 지점에 있는 보석의 갯수를 +1 해준다. 

 (5-3) end 지점을 +1 증가시킨다. 

 

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    unordered_map<string,int> gemlist; 
    int st = 0, end = 0;
    for(auto gem : gems) gemlist[gem] = 0;
    int total = gemlist.size(), cnt = 0, temp_st=0, temp_end=0, maxi = 1e9;
    while(true){
        if(cnt==total){
            if(end-st<maxi){ // 1
                temp_st = st;
                temp_end = end;
                maxi = end-st;
            }
            if(gemlist[gems[st]]>1){ // 2
                gemlist[gems[st]]--;
                st++;
            }
            else{
                gemlist[gems[st]]--; // 3
                st++;
                cnt--;
            }
        }
        else if(end==gems.size()) break; // 4
        else{
            if(!gemlist[gems[end]]) cnt++; // 5
            gemlist[gems[end]]++;
            end++;
        }
    }
    answer.push_back(temp_st+1); answer.push_back(temp_end);
    return answer;
}

채점했을 때 계속해서 틀렸는데, 이유는 end - st <maxi를 end - st <= maxi로 설정했기 때문이다. 

여러개의 정답이 있을 경우 가장 빠른 값, 즉, 작은 숫자를 답으로 채택해야하는데 이를 간과하여 가장 큰 정답값을 출력했다.