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

 

 

#문제 간단 정리

 

브루트 포스로는 시간초과와 효율성으로 엉망일게 보이니

투 포인터/슬라이딩 윈도우를 활용하자

 

 

#문제 해결 방법

 

우선 사실 구간을 [1,3] [2,4] 이런식으로 출력 하라는 것 자체가

어쩌면 투 포인터 사용에 대한 힌트일지도 모른다.

 

1.우선 전체 보석의 종류의 개수를 센 뒤에.

2. 투 포인터를 사용한다

 만약 현재 보석의 모든 개수를 포함한다면

 left를 증가시키고 

보석의 종류가 부족하다면 right 를 증가시키면 된다.

 

2-1 

 여기서 보석종류에 따른 개수를

map 으로 기록해주는데

만약 left가 한칸 올라가서 map에 있는 보석종류의 개수가 0이되었다면

전체 보석의 개수를 기록하고 있는 변수를 (currenTypes)를 -1 해주면된다

 

반대로 right 한칸 올라가서 보석종류의 개수가 0개였다면

전체 보석의 개수를 기록하고 있는 변수를 (currenTypes)를 +1 해주면된다

 

이 작업은 효율성 때문에 이뤄지는 작업이다.

현재 가지고있는 보석의 종류 개수를 쉽게 카운트 하기 위해서.

 

나머지는 전체 코드를 보고 이해하는게 쉬울것이다.

 

 

#전체 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <climits>
#include <set>

using namespace std;

vector<int> solution(vector<string> gems) {
    unordered_map<string, int> gemCount;
    set<string> gemTypes(gems.begin(), gems.end());
    int totalTypes = gemTypes.size();
    
    int minlength = INT_MAX;
    pair<int, int> index;
    
    // 투 포인터, 슬라이딩 윈도우를 활용
    int l = 0, r = 0;
    int currentTypes = 0;
    
    while (true) {
        if (currentTypes == totalTypes) { // 모든 종류의 보석이 포함되었을 때
            if (minlength > r - l) {
                minlength = r - l;
                index = make_pair(l, r);
            }
            if (--gemCount[gems[l]] == 0) {
                currentTypes--;
            }
            l++;
        } else { // 모든 종류의 보석이 포함되지 않았을 때
            if (r == gems.size()) break; // 종료 조건
            if (gemCount[gems[r]]++ == 0) {
                currentTypes++;
            }
            r++;
        }
    }
    
    vector<int> answer = {index.first + 1, index.second};
    return answer;
}