[프로그래머스] 보석 쇼핑 (C++)

문제 링크: programmers.co.kr/learn/courses/30/lessons/67258

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

1. 주의할 점

- 두 포인터를 이용하여 해결한다

- 포인터를 옮길때마다 왼쪽~오른쪽 포인터까지 탐색하지 않도록 한다

 

2. 구현

- Map을 이용하여 보석과 숫자를 매칭시킨다

- V 벡터를 이용하여 숫자에 해당하는 보석이 몇개 존재하는지 나타낸다

- 0번째 인덱스에 존재하는 보석을 미리 처리하고 시작한다

- While문을 통해 R 포인터가 Gems의 길이보다 작을때까지 수행한다. 내부 While문은 보석 전체가 1개 이상씩 있을때 혹은 R이 오른쪽 끝에 위치해 있을때 들어갈 수 있도록 설정한다. minLen을 갱신시킬 수 있다면 갱신시키고 L이 R과 같지 않다면 L을 오른쪽으로 하나 옮기고, 기존에 L이 가리키던 보석의 개수를 1 감소시키고 해당 보석의 개수가 0이되면 Cnt--한다

- R 포인터를 오른쪽으로 한칸씩 옮기며 해당 포인터가 가리키는 보석의 수를 1 증가시키고, 기존에 없던 보석이라면 Cnt++한다

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

vector<int> solution(vector<string> gems) {
    vector<int> answer,v;
    map<string, int> m;
    int num=0;
    for(int i=0;i<gems.size();i++){
        string str = gems[i];
        if(m[str]==0)
            m[str] = ++num;
    }
    for(int i=0;i<=num;i++)
        v.push_back(0);
    int l=0,r=0,cnt=1,len = gems.size(),minLen = len+1,L=0,R=0;
    string sr,sl;
    int idx = m[gems[0]];
    v[idx]++;
    while(r<len){
        while(num==cnt || r+1==len){
            if(minLen>r-l && num==cnt){
                minLen = r-l;
                R=r;
                L=l;
            }
            if(l==r) break;
            int idx = m[gems[l++]];
            v[idx]--;
            if(v[idx]==0) cnt--;
        }
        if(r+1==len) break;
        int idx = m[gems[++r]];
        v[idx]++;
        if(v[idx]==1) cnt++;
    }
    answer.push_back(L+1);
    answer.push_back(R+1);
    return answer;
}