2020 Kakao internship 67258 - 보석 쇼핑(슬라이딩 윈도우) c++

 

- 특정 범위의 보석을 모두 챙기는데 모든 종류의 보석을 챙기는 가장 짧은 범위를 찾는 문제이다.

- 문제에서 보석 배열 길이가 10만이므로 10만^2 = 100억이므로 nlogn 이하 로직을 사용해야한다. 그렇기 때문에 어떤 범위가 이동하면서 그 범위 안의 구간합 등이 조건에 성립하는지를 O(N)으로 구할 수 있는 슬라이딩 윈도우 방식으로 접근하였다. 

- 전체 보석 종류 갯수를 구한다. 그 종류 갯수는 어떤 범위가 모든 보석종류를 모두 포함하는 최소길이의 범위가 될 것이다. 인덱스 0부터 모든 보석종류를 포함하는지를 map을 통해서 체크한다. map을 사용하는 이유는 2개 이상의 같은 종류보석이 들어있을 수 있기 때문이다. 
모든 종류 보석이 있는 범위가 구해지면 거기서 1칸씩 전진하면서 전진하는 방향 인덱스의 보석을 추가하고 뒤 인덱스 보석을 소거하면서 점차 범위를 줄여나간다. 

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

using namespace std;

// 진열된 모든 종류의 보석을 포함하는 가장 짧은 range 찾기
vector<int> solution(vector<string> gems) { // length 10만. 10만^2 = 100억
    vector<int> ans;
    
    unordered_set<string> uset;
    for(string& s: gems) {
        uset.insert(s);
    }

    int nType = uset.size(); // 보석 종류갯수
    int s = 0, e = 0, i = 0, range = 100000; //gem 배열10만
    unordered_map<string, int> umap; // 범위내 보석 카운트
    
    while(1) { // 슬라이딩 윈도우
        for(i = e; i < gems.size(); ++i) {
            ++umap[gems[i]];
            if(umap.size() == nType) { // 보석 종류 다 모았으면 종료
                e = i;
                break;
            }
        }
        
        if(i == gems.size()) break; // 범위 벗어남
        
        for(i = s; i < gems.size(); ++i) {
            if(umap[gems[i]] == 1) {
                s = i;
                break;
            } else {
                --umap[gems[i]];
            }
        }
        
        if(e - s < range) {
            ans = {s + 1, e + 1};
            range = e - s;
        }
        
        umap.erase(gems[s]);
        ++s, ++e;
    }
    
    return ans;
}

https://programmers.co.kr/learn/courses/30/lessons/67258

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