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

처음 문제를 봤을 때 set이나 map을 사용해야 될 것 같긴 했는데 전반적인 풀이 방법이 떠오르지 않아 다른 사람 코드를 참고했습니다. 효율성을 따진다는 것 + 보석의 개수가 최대 10만 개라는 점에서 모든 경우를 다 탐색한다는 것은 시간 초과가 날 것이라 생각했고, 풀이를 보니 투 포인터를 사용하는 것이었습니다.

투 포인터 문제를 많이 풀어보지는 않았지만 보석 쇼핑과 같이 연속되는 데이터를 찾는 문제(?) 유형에 많이 사용되는 것 같습니다.

풀이 방법

1. map에 보석의 종류와 개수를 담아줍니다.
2. 보석의 종류를 중복 없이 담기 위해서 set을 사용합니다. 아래와 같이 set을 선언하면 gems vector의 처음부터 끝까지 중복되지 않게 데이터를 set에 담아줍니다.
3. 보석의 종류를 다 포함하는 최소의 end 위치를 구합니다. 입출력 예의 1번으로 치면 "DIA[인덱스 0번]부터 SAPPHIRE[인덱스 6번] 까지를 의미 합니다. map에 보석이 다 담기게 되면 map의 size는 set의 size와 같게 됩니다. 그 상태의 i를 end로 지정합니다.
4. 구해진 end에서 start를 빼서 minDist 변수를 초기화합니다.
5. 투 포인터를 진행할 때 start의 위치를 오른쪽으로(end 쪽으로) 한 칸씩 이동하면서 최소의 길이를 구하게 되는데 이때 start가 움직여도 map의 size는 여전히 전체 보석의 개수(set의 size)와 같아야 합니다. start가 이동하면 원래 start 위치에 있던 보석의 개수가 하나 줄어드는데 개수가 한 개 줄어듦으로써 map의 size가 set의 size와 달라진다면 end를 오른쪽으로 이동합니다. 코드에서는 map의 value 값이 0이라면 보석이 하나도 없는 것을 의미합니다.
6. end가 오른쪽으로 이동하더라도 gems vector의 size 이상으로는 움직일 수 없기 때문에 while문의 조건을 end < gems.size()로 지정했습니다.
7. map의 size가 다시 set의 size와 같아질 때까지 end를 오른쪽으로 움직이면서 end 위치의 보석을 map에 담아줍니다.
8. end-start가 기존의 minDist보다 작다면 end와 start를 다시 answer 변수에 대입합니다. 

#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

vector<int> solution(vector<string> gems) {
    map<string, int> zmaps;
    vector<int> answer;
    set<string> zsets(gems.begin(), gems.end());
    
    int zsets_size = zsets.size();
    int start =0, end = gems.size()-1;
    
    // 보석을 다 포함하는 end를 구함
    for(int i=0;i<gems.size();i++){
        zmaps[gems[i]]++;
        if(zsets_size == zmaps.size()){
            end = i;
            break;
        }
    }
    
    answer  = {start+1, end+1};
    int minDist = end - start;
    
    
    while(end < gems.size()){
        string gem = gems[start];
        zmaps[gem]--;
        start++;
        
        if(zmaps[gem] == 0){
            end++;
            while(end < gems.size()){
                zmaps[gems[end]]++;
                if(gems[end] == gem){
                    break;
                }
                end++;
            }
        }
        
        if(end-start < minDist){
            answer = {start+1, end+1};
            minDist = end-start;
        }   
    }
    return answer;
}