[프로그래머스 lv3] 보석 쇼핑 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

 

해설

해당 문제는 2020 카카오 인턴십에 출제되었던 문제로 공식 해설이 있습니다.

2020 카카오 인턴십 for Tech developers 문제해설

 

처음에는 이분탐색 + 슬라이딩 윈도우 기법으로 O(NlogN)에 해결하였으나, 이상하게 WA + TLE 이 떠서 결국 투포인터 방법으로 해결하였다.

 

왼쪽 포인터 l과 오른쪽 포인터 r을 0번 진열대에 위치시키고, map<string, int> m; 에 0번 진열대의 보석 개수를 1로 기록한다.

이후, [l, r] 구간이 모든 종류의 보석을 포함하고 있는지 확인한다.

 

1) 만약, [l, r] 구간이 모든 종류의 보석을 포함하고 있다면, 길이가 r-l+1인 [l, r] 구간을 기록하고 l을 오른쪽으로 하나 이동시켜 구간의 길이를 줄여본다.

2) 만약 [l, r] 구간이 모든 종류의 보석을 포함하고 있지 않다면, r을 오른쪽으로 하나 이동시켜 구간의 길이를 늘여본다.

 

[l, r] 구간에 모든 종류의 보석이 있는지 확인하기 위해서는, map<string, int> 에 보석별 등장 횟수를 기록하고 map의 크기가 '중복을 제거한 보석 집합의 길이'와 같은지 체크하면 된다. 주의할 것은, map[보석] = 0 이 되었을 때, map 내부에 해당 보석의 정보가 남아있지 않도록 해당 원소를 제거해야 한다는 것이다.

 

이후, {길이, l, r} 정보를 기록한 배열을 정렬시키고, 길이가 가장 짧으면서 l이 가장 작은 구간을 리턴하면 정답이다.

 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<int> solution(vector<string> gems) {

    set<string> sset;
    for (auto x : gems) sset.insert(x);

    map<string, int> m;

    int l = 0, r = 0;
    m[gems[0]]++;
    vector<iii> v;

    while (l <= r && r < gems.size()) {
        if (m.size() == sset.size()) { 
            //[l, r] 구간이 모든 보석을 포함하고 있을 때 l을 오른쪽으로 이동            
            v.push_back({r-l+1, l, r});
            m[gems[l]]--;
            if (m[gems[l]] == 0) 
                m.erase(gems[l]);
            l++;
        }
        else { 
            //[l, r] 구간이 모든 보석을 포함하고 있지 않을 때 r을 오른쪽으로 이동
            r++;
            if (r < gems.size()) m[gems[r]]++;
        }
    }

    sort(v.begin(), v.end());
    return {get<1>(v[0])+1, get<2>(v[0])+1};
}