[21/10/24] 보석쇼핑

아이디어

-> 최적화 문제이기에 가장 먼저 투포인터, 슬라이딩 윈도우를 생각해봄.

-> 투포인터 알고리즘을 사용하여, 모든 종류의 보석이 담길때까지 오른쪽 포인터를 늘리다가.

-> 모든 종류의 보석이 담기게 되면, 최소 길이 구간을 찾기 위해 좌측 포인터를 늘린다.

1. 좌측 포인터 - 우측 포인터 까지를 Array로

2. 좌측 포인터 - 우측 포인터 까지를 Map으로

3. 좌측 포인터 - 우측 포인터 까지를 Set으로

여러 가지 자료구조로 도전해보았는데, 배열의 경우 시간초과가 발생한다. 이차 시간이됨.

Set으로 구현하게 되면, 중복이 제거되는 특징 때문에, 몇개가 포함된 것인지를 따로 저장해주어야한다.

Map(객체)으로 구현 결정하였다.

나의 코드

function solution(gems) {
    let answer = []
    let jewels = {}
    gems.forEach((i)=>{
        jewels[i] = true;
    })
    
    jewels = Object.keys(jewels);
    

    let left = 0;
    
    let right = 0;
    
    let min = 100000000;
    
    const map = new Map();
    
    while( left <= right && right<=gems.length){
        
        if(map.size === jewels.length){
          // 5개가 되었으므로 좌측을 늘린다.  
          
          	const key = gems[left];
            
            answer.push([left,right-1,right-1-left]);
            // 최솟값 저장
            min = Math.min(right-left-1,min);
            
            if(map.get(key) === 1){
                // 한개라면 키를 지워버려 모든 상품이 포함된 것이 아니도록 만들어야함.
                map.delete(key);
                
            }else{
                // 한개가 아니라면, 중복으로 여러개들어와있는 것이므로 갯수를 줄인다.
                map.set(key, map.get(key)-1)
                
            }
            
            left++;
            
        }else{
          
        // 5개가 안되면 오른쪽을 늘린다.
          
            const key = gems[right]
            // 이미 있으면 +1, 아니면 1 
            map.set(key,map.get(key) ? map.get(key) + 1 : 1)
            
            right++;
            
        }
        
    }
  
    // 최솟 값 중 가장 먼저 나온 것이, left(시작 지점)이 가장 작은 요소임.
    const result = answer.find(([,,diff])=>{
        return diff === min 
    })
    
    // 리턴
    return result && [result[0]+1,result[1]+1]
}

리팩토링

• answer.find 하여 min 값을 추출해내는 로직을 제거(객체를 활용하였다. 거리가 키값이 되어 가장 먼저 등장하는 요소만을 값으로 갖는다. 조회시 최단 거리 중 시작 지점이 가장 낮은 값

• gemVariety 부분을 set을 활용하여 구현

function solution(gems) {
    
    let gemVariety = new Set(gems).size;

    let left = 0;
    
    let right = 0;
    
    let min = Number.MAX_SAFE_INTEGER
    
    const map = new Map();
    
    const answer = {};
    
    while( left <= right && right<=gems.length){
        // 5개가 되면 왼쪽을 늘린다.
        // 5개가 안되면 오른쪽을 늘린다.
        // 5개가 되는 시점에 answer 배열에 추가한다.
        if(map.size === gemVariety){
            const key = gems[left];
            
            
            
            min = Math.min(right-left-1,min);
            
            if(answer[right-left-1] === undefined){
                
               answer[right-left-1] = [left+1,right];
                
            }
            
            if(map.get(key) === 1){
                
                map.delete(key);
                
            }else{
                
                map.set(key, map.get(key)-1)
                
            }
            
            left++;
            
        }else{
            const key = gems[right]
            
            map.set(key,map.get(key) ? map.get(key) + 1 : 1)
            
            right++;
            
        }
        
    }
  
    return answer[min]
}