보석 쇼핑 - 투포인터

programmers.co.kr/learn/courses/30/lessons/67258

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

<처음 풀이법 - 이진탐색, 효율성 실패>

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

vector<int>v;
vector<int> answer;

bool includeAll(vector<string>&gems, int m,int sz){
    
   
    for(int i=0; i<=gems.size()-m; i++){
        int j=i+m-1;
        if(j<0){break;}
        set<string>s;
        for(int t=i; t<=j; t++){
         
           s.insert(gems[t]);
            
        }
        
        if(s.size()==sz){v.push_back(i+1); v.push_back(j+1); return true;}
    }
    
     return false;
    
}


vector<int> solution(vector<string> gems) {
    
    set<string>alltype;

    int sz=0;
  
    for(int i=0; i<gems.size(); i++){
        if(alltype.find(gems[i])==alltype.end()){
           alltype.insert(gems[i]);
           
        }
    }
    
    sz = alltype.size();

    if(sz==1){answer.push_back(1); answer.push_back(1); return answer;}
    
    int st = sz;
    int e= gems.size();
    
  
        
    while(st<=e){
       
        int m = (st+e)/2;
        if(includeAll(gems,m,sz)){
              answer =v;
              v.clear();
              e = m-1;
        }
        else{ 
                st= m+1;

        }
    
    }

    return answer;
}

<투포인터를 사용한 풀이법-통과>

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




vector<int> solution(vector<string> gems) {
    
    vector<int>answer;
    map<string,int>m;
    set<string>ss;
    int s=0; int e=0;
    
    for(int i=0; i<gems.size(); i++){
        ss.insert(gems[i]);
    }
  
    int sz = ss.size();

    int tmps,tmpe;
    int len = 999999999;
    while(1){
        if(m.size()==sz){
            if(e-s<len){
                tmps =s;
                tmpe =e;
                len = e-s;
            }
            
            if(m[gems[s]]>1){
                m[gems[s]]--;
                s++;
            }
            else{
                m.erase(gems[s]);
                s++;
            }
        }else{
            if(e==gems.size())break;
            m[gems[e]]++;
            e++;
        }
    }
    answer.push_back(tmps+1);
    answer.push_back(tmpe);
    return answer;
}

- s와 e가 0에서 시작해서 만약에 집합 s 와 맵 m에있는 숫자가 같으면 s를 늘려주고 아니면 e를 늘려준다

 

<java code>

import java. util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        HashSet<String> hs = new HashSet<>();
        HashMap<String,Integer>hm = new HashMap<>();
        for(int i=0; i<gems.length; i++){
            hs.add(gems[i]);
        }
        
        int n = hs.size();
        int s =0;
        int e =0;
        int as =0;
        int ae =gems.length-1;
    
    //    System.out.println(n);
        
        hm.put(gems[0],1);
        
        while( s<=e && e<gems.length){
        //    System.out.println(s+","+e);             
            if(hm.size()>=n){
                if(hm.size()==n){
                    if(((e-s)<(ae-as))||as==0){
                              // System.out.println(s); 
                    as=s+1;
                    ae=e+1;
                    }
                }
                if(hm.containsKey(gems[s])){
                hm.put(gems[s],hm.get(gems[s])-1);
                if(hm.get(gems[s])==0){
                        hm.remove(gems[s]);
                    }    
                } 
                
                
                s++;
              }
            else if(hm.size()<n){
                e++;
                if(e>=gems.length){break;}
                if(hm.containsKey(gems[e])){
                    hm.put(gems[e],hm.get(gems[e])+1);
                }
                else{
                    hm.put(gems[e],1);
                }
             }
            
            
        }
        answer[0]=as;
        answer[1]=ae;
        
        return answer;
    }
}