C++:: 프로그래머스 < 보석 쇼핑 >

로직을 생각하는게 중요한 문제이다. 해당 코드의 핵심은 시작과 끝 인덱스를 기준으로 기준에 부합하면 기억을 해주고, 시작인덱스와 끝 인덱스를 적절히 미루면서 최소 구간을 찾는 방식이다.

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

vector<int> solution(vector<string> gems) {
    vector<int> answer(2, 0); answer[1] = INT32_MAX;
    unordered_map<string, int> us;
    for (auto& gem : gems) {// 보석 이름, 개수(현재 구간에서 들고있는) 등록
        us[gem] = 0;
    }
    
    int gem_num=us.size(), s=0, cur_gems=0;

    for (int e=0; e<gems.size() && s <= e;) {
        if ((s != e && gems[s] == gems[e]) || us[gems[s]] > 1) {// 시작 끝 보석이 같거나 시작보석이 한개보다 많다면(구간 중간에 중복한 보석이 있다면)
            if (!(--us[gems[s++]])) cur_gems--;// 시작부분 보석을 빼주고 들고있지 않는다면 전체 개수에서도 빼준다.
            continue;
        } else if (!us[gems[e]]++) { // 보석을 최초로 구간에서 들게 된다면
            cur_gems++;
        }
        if (cur_gems == gem_num) {
            if (answer[1]-answer[0] > e-s) {// 모든 종류의 보석을 들었고 구간이 더 짧다면 정답 갱신
                answer[0] = s+1;
                answer[1] = e+1;
            }
            if (!(--us[gems[s++]])) cur_gems--;// 시작 인덱스 미뤄주면서 개수 빼주기
        }
        e++;
    }

    return answer;
}