프로그래머스) Lv3 - 보석 쇼핑 [2020 카카오 인턴십]

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

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

투포인터 알고리즘을 이용해 gems Vector를 탐색하며 Map으로 현재 가진 보석의 수를 체크해주었습니다.

---

C++ 소스 코드

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

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    map<string, int> mp;
    for(int i=0;i<gems.size();i++){
        mp[gems[i]]=0;
    }
    int jSize = mp.size();
    int r = 0, l = 0;
    int last = (int)gems.size();
    int nowcnt = 0;
    answer.push_back(0);
    answer.push_back(last);
    while(true){
        if (nowcnt >= jSize){
            if(mp[gems[l]]-1==0){
                nowcnt--;
            }
            mp[gems[l++]]--;
        } else if (r == last) break;
        else {
            if(mp[gems[r]]==0) nowcnt++;
            mp[gems[r++]]++;
        }
        if(nowcnt == jSize) {
            if (r-l < answer[1]-answer[0]){
                answer[0]=l;
                answer[1]=r;
            }
        }
    }
    answer[0]++;
    return answer;
}