[프로그래머스 Level_3 / C++ / 카카오] 보석 쇼핑

투포인터를 활용해서 풀었다. 

 

1. 먼저 본인은 문자열을 상당히 싫어하기 때문에 unordered_map 을 활용해서 문자열을 모두 숫자로 변경하였다. 

 - 즉, 위의 예제에서 나오는 보석이름을 숫자로 변경해서 v라는 벡터에 저장하였다. 

 

  gams {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"} =>  v { 1, 2, 2, 1, 1, 3, 4, 1 }  

 

2. START, END 변수를 생성하여 벡터의 인덱스 번호를 저장 시킨 후, 문자열 종류의 개수에 도달하지 않았다면 END변수를 계속해서 증가 시켜준다.  ( 위의 예제에서 문자열 종류의 개수는 4개이다. ) 

이때, 방문했던 값을 인덱스로 가진 check 라는 벡터에 개수를 하나씩 증가시켜준다.  

 

3. 문자열 종류의 총 개수가 충족되면 START 변수의 값을 하나씩 증가시켜주면서 시작 포인터를 우측으로 이동한다. 

이때, 이전에 check 라는 벡터에서 지금까지 나왔던 문자열의 개수를 하나씩 감소시켜주면서 해당 값이 0이 되는 순간 문자열 종류의 전체 개수를 충족시켜주지 못하는 순간이다. 이 때 s와 e의 차이값이 최종 길이이며 해당 길이가 최소인 경우 result 에 값을 저장한다. 

 

#include <string>
#include <vector>
#include <map> 
#include <unordered_map>
#include <iostream>
#include <algorithm>
using namespace std;
int check[100001];
unordered_map <string, int> m; 
vector<int> solution(vector<string> gems) {
    vector<int> answer(2,0);
    vector <int> v (gems.size(), 0);
    int pos =1; 
    for(int i=0; i<gems.size(); i++){
        if(m[gems[i]]==0){
            m[gems[i]]= pos++; 
            v[i]=m[gems[i]];         
        }
        else v[i]=m[gems[i]];        
    }   
    int total = m.size(); // 문자열의 개수
    int s, e, cnt, len =1; 
    cnt = s = e= 0; 
    int min_len=1000000;    
    while(e<v.size()){            
        if(!check[v[e]]){
            cnt++; check[v[e]]++; e++;  
        }
        else if(check[v[e]]){
            check[v[e]]++; e++; 
        }              
        if(total ==cnt){
            while(check[v[s]]>0){
                check[v[s]]--; 
                if(check[v[s]]==0){
                    s++; 
                    break;
                } 
                s++;            
            }
            cnt--;             
            if(e-s<min_len){          
                min_len = e-s; 
                answer[0]=s; 
                answer[1]=e;      
            }
        }       
    }           
    return answer;
}

 

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