[프로그래머스] Level 3. 보석 쇼핑

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

프로그래머스

 

해결 방법

• 보석이 총 몇종류인지 구한다. (totals.size())
• 진열대를 돌면서 , counts에 보석개수를 증가한다. counts는 내가 head 부터 i까지 보석 개수를 의미한다.
• i번째를 구매하고, head에서부터 뺄수있는지 검사하여 head를 당길 수 있다면 당긴다. head에 있는 보석이 2개이상 이라면, head번째는 구매하지않고 head+1부터 구매해도 상관없다는 의미이다.
• counts 에 있는 보석의 종류가 totals.size() 와 동일하다면 답을 갱신해준다. 최솟값을 찾는것이므로, 최솟값일때만 답을 갱신해준다.

 

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

vector<int> solution(vector<string> gems) {
    vector<int> answer(2,INT_MAX);
    map<string,int> counts;
    set<string> totals;
    for(int i= 0; i<gems.size(); i++){
        totals.insert(gems[i]);
    }
    
    int head = 0;
    for(int i=0; i<gems.size(); i++){
        counts[gems[i]] += 1;
        
        while(true){
            string gem = gems[head];
            if(counts[gem] <= 1) break;
            
            counts[gem]--;
            head++;
        }
        
        if(counts.size() == totals.size()){
            if(answer[0] == INT_MAX || i-head < answer[1]-answer[0]) {
                answer[0] = head; answer[1] = i;
            }
        }
    }
    
    answer[0] += 1;
    answer[1] += 1;
    return answer;
}