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

문제

프로그래머스 2020 카카오 인턴십 - 보석 쇼핑 (Level 3)

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

 

---

문제 풀이

접근 방식

모든 보석을 하나 이상 포함하는 가장 짧은 구간을 구하는 문제이다.

 

문제를 해결하기 위해 우선, unordered_set을 이용하여 보석 종류의 개수를 구하였다.

그 후, for을 수행하며 unordered_map에 각 보석의 인덱스를 저장해주었다.

처음으로 모든 종류의 보석을 발견했을 때,

map에 저장되어 있는 인덱스의 최솟값을 answer의 시작 구간, 현재 인덱스(i + 1)를 끝 구간으로 저장해주었다.

또한, 이때의 최솟값의 보석 종류를 MIN_gen에 저장해두었다.

 

MIN_gen에 저장해둔 보석을 발견하는 경우는 최소 인덱스가 변경되는 경우이다.

이때마다 구간을 구하는 위의 과정을 반복하였고,

더 짧은 구간인 경우 answer의 값을 바꿔주며 문제를 해결하였다.

 

---

풀이 코드 - C++

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

vector<int> solution(vector<string> gems) {
    // 보석 종류 개수 구하기
    int len = gems.size();
    unordered_set<string> gem_set;
    for(int i = 0; i < len; i++)
        gem_set.insert(gems[i]);
    int total = gem_set.size();
    
    // 가장 짧은 구간 구하기
    int cnt = 0;
    int MIN_len;
    int MIN;
    string MIN_gem;
    vector<int> answer(2);
    unordered_map<string, int> dic;
    for(int i = 0; i < len; i++){        
        MIN = i+1;
        if(dic[gems[i]] == 0){  // 새로운 보석 종류 발견 시
            cnt++;
            dic[gems[i]] = i+1;
            if(cnt == total){
                for(auto d : dic) {
                    if(MIN > d.second){
                        MIN = d.second;
                        MIN_gem = d.first;
                    }
                }
                answer[0] = MIN;
                answer[1] = i + 1;
                MIN_len = i + 1 - MIN;
            }
            continue;
        }
        
        dic[gems[i]] = i+1;
        if(cnt == total && MIN_gem == gems[i]){ // 최솟값 인덱스 변경 시
            for(auto d : dic) {
                if(MIN > d.second){
                    MIN = d.second;
                    MIN_gem = d.first;
                }
            }
            if(MIN_len > i + 1 - MIN) {
                answer[0] = MIN;
                answer[1] = i + 1;
                MIN_len = i + 1 - MIN;
            }
        }
    }
    
    return answer;
}

실행 결과

실행 결과 : 100.0