(코테) 프로그래머스_보석 쇼핑 *윈도우슬라이딩

 

문제 링크

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/67258

 

 

1. 최초 제시한 답

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {        
        
        Set<String> set = new HashSet<>();
        for(String next:gems) set.add(next);
        int len = set.size();
        
        //Map을 쓰는 이유는 구간중에 중복된 값들이 존재할 수 있으므로.
        Map<String,Integer> jewelryList = new HashMap<>();
        
        int left =0;
        int leftBest =0;
        int rightBest =0;
        
        // 0~gems.length까지
        //첨부터 가능한 구간까지 오른쪽 늘림.
        for(int right=0;right<gems.length; right++){            
            String rk = gems[right];
            Integer rc = jewelryList.get(rk);
            if(rc==null) jewelryList.put(rk,1);
            else jewelryList.put(rk, rc+1);

                
            //모든 보석을 가지고 있다면! (왼쪽 줄이기 + 값 갱신 체킹)
            while(jewelryList.size()==len){
                
                //가장 짧은 구간 갱신
                //가장 최적화된 범위 기억(BSET 변수) 하고 갱신 시키기 
                if(rightBest==0 || (right-left) < (rightBest-leftBest)){
                    leftBest=left+1;
                    rightBest=right+1;                    
                }
                
                //왼쪽 줄이기 (map 값 제거 + left값 ++ )
               String lk =  gems[left];
               int lc = jewelryList.get(lk);
                if(lc==1) jewelryList.remove(lk); 
                else  jewelryList.put(lk , lc-1);     
                
                left++;
   
            }            
            
        }  
        
        //for문 다 돌면(오른쪽 구간 다 돌았으면) 종료
        
        return new int[]{leftBest,rightBest};
    }
}

 

 

 

 

2.리팩토링 한 답

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {        
        
        Set<String> set = new HashSet<>();
        for(String next:gems) set.add(next);
        int len = set.size();
        
        //Map을 쓰는 이유는 구간중에 중복된 값들이 존재할 수 있으므로.
        Map<String,Integer> jewelryList = new HashMap<>();
        
        int left =0;
        int leftBest =0;
        int rightBest =0;
        
        // 0~gems.length까지
        //첨부터 가능한 구간까지 오른쪽 늘림.
        for(int right=0;right<gems.length; right++){            
                
            if(jewelryList.containsKey(gems[right])) jewelryList.put( gems[right], jewelryList.get(gems[right])+1);
            else  jewelryList.put(gems[right],1);
                
            //모든 보석을 가지고 있다면! (왼쪽 줄이기 + 값 갱신 체킹)
            while(jewelryList.size()==len){
                
                 //가장 짧은 구간 갱신
                //가장 최적화된 범위 기억(BSET 변수) 하고 갱신 시키기 
                if(rightBest==0 || (right-left) < (rightBest-leftBest)){
                    leftBest=left+1;
                    rightBest=right+1;                    
                }
                
              //왼쪽 줄이기 (map 값 제거 + left값 ++ )
            if(jewelryList.get(gems[left]) == 1) jewelryList.remove(gems[left]); 
            else  jewelryList.put( gems[left], jewelryList.get(gems[left])-1);     
            
                left++;
            }            
            
        }
        
        //for문 다 돌면(오른쪽 구간 다 돌았으면) 종료
        
        return new int[]{leftBest,rightBest};
    }
}