[슬라이딩 윈도우] 프로그래머스 보석 쇼핑 C++

 

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

슬라이딩 윈도우

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

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer = {100000, 100000};

    unordered_map<string, int> mp;
    set<string> s;
    for(auto g : gems) s.insert(g);

    int n = gems.size();
    int type = s.size();

    int end = 0;
    int dist = n + 1;
    for(int start=0; start<n; start++) { // 슬라이딩 윈도우 방식
        while (mp.size() < type) {
            if (end >= n) break;
            if (mp.find(gems[end]) != mp.end()) mp[gems[end]]++;
            else mp.insert({gems[end], 1});
            end++;
        }

        if (mp.size() == type) { // while문 바깥
            if ((dist > end - start) || ((dist == end - start) && (answer[0] > start + 1))) {
                dist = end - start;
                answer = {start + 1, end};
            }
        }

        mp[gems[start]]--;
        if (!mp[gems[start]]) mp.erase(mp.find(gems[start]));
    }

    return answer;
}

구간합

효율성 실패

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

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    
    unordered_map<string, int> mp;
    for(auto g : gems) mp.insert({g, mp.size()});
    
    int type = mp.size();
    int n = gems.size();
    int arr[n+1][type];
    fill(&arr[0][0], &arr[n][type], 0);

    for(int i=0; i<n; i++) {
        int idx = mp[gems[i]];
        arr[i+1][idx]++; // 시작점 포함, 끝점 미포함
        for(int j=0; j<type; j++) arr[i+1][j] += arr[i][j];
    }
    
    int start = 0;
    int end = 1;
    int dist = n + 1;
    while(start < end) { // 누적합 인덱스 ex) 3-1 = [1,2]
        if ((start > n) || (end > n)) break;
        
        int cnt = 0;
        for(int j=0; j<type; j++) {
            if (arr[end][j] - arr[start][j] > 0) cnt++;
        }

        if (cnt == type) {
            if (dist > (end - start)) {
                dist = end - start;
                answer = {start + 1, end};
            }
            start++;
        }
        else if (cnt < type) end++;
        else start++;
    }
    
    return answer;
}