카카오 보석쇼핑

문제설명

보석이 일렬로 진열돼있고, 연속으로 선택한다 할 때
모든 종류의 보석을 포함하는 가장 짧은 구간을 찾는 문제

진열대가 위와 같다면 3467을 선택하면 모든 종류의 보석을 선택하게 되고, 연속 선택해야 하므로 답은 3 7이 된다

풀이

투포인터로 탐색하면서 map stl에 보석을 넣고 빼면서 모든 종류를 포함하는 최소길이를 찾는다

설명
1. 한번 순환하면서 보석 종류 수 알아놓음

1. 앞의 포인터 한칸 옮김 ( 추가됨)

   • 이미 있는 보석 (m.find(gem) !=m.end())
     뒤의 포인터와 추가된 보석이 다르다면 끝
     같다면 while문으로
     m[gem]이 1이 아니라면 back을 한칸 앞으로 전진
     m[gem]-- 해줌

   • 없는 보석 (m.find(gem) ==m.end())
     모은 보석 종류 ++

2. 모든 보석 종류 모았다면
   최소 길이에 따라 갱신, 포인터 앞뒤 저장해둠
   

코드

#include <string>
#include <vector>
#include <map>
#include <string.h>
#include <stdlib.h>
using namespace std;

map<string,int> m;
map<string,int> M;
int cnt; // 종류 수
vector<int> solution(vector<string> gems) {
    vector<int> answer;
    for(int i=0;i<gems.size();i++){
        if(m.find(gems[i])==m.end()){ //없음 
            m.insert(make_pair(gems[i], 1));
            cnt++;
        }
    }
    
    // for(auto iter = m.begin();iter!=m.end();iter++){
    //     printf("%d\n",iter->second);
    // }
    int back =-1;
    int sum =0;
    int min = 99999;
    int f,b;
    for(int i=0;i<gems.size();i++){ //추가 포인터 위치
        if(M.find(gems[i])!=M.end()){ // 있음 
            M[gems[i]]++;
            if(gems[back+1].compare(gems[i])==0){
                while(1){
                    if(M[gems[back+1]]>1){
                        back++;
                        M[gems[back]]--;
                    }else{
                        break;
                    }
                }
            }
        }else{ // 없음 
            M.insert({gems[i],1});
        }
        if(M.size()==cnt){ // 종류 다 들어와있음 
            if(i-back< min){ // 갱신 
                min = i-back;
                f=i;
                b=back;
            }
        }
        // printf("%d %d\n",back,i);
    }
    answer.push_back(b+2);
    answer.push_back(f+1);
    return answer;
}