프로그래머스: 보석 쇼핑 - javascript(슬라이딩 윈도우)

문제 출처 

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

프로그래머스

 

시간 초과 코드

function solution(gems) {
    let set = [...new Set(gems)];
    let n = set.length; 
    for(let i=n; i<=gems.length; i++){ 
        let sIdx = 0; 
        while(sIdx+i <= gems.length){
            if(check(gems.slice(sIdx, sIdx+i), set)) return [sIdx+1, sIdx+i]
            sIdx++; 
        }
    }
}

function check(arr,set){
        if([...new Set(arr)].length === set.length) return true; 
        else return false; 
    }

 

Map 객체 사용 

function solution(gems) {
    let answer = [1,gems.length];
    const minGemsNum = new Set(gems).size;
    const gemMap = new Map();
    
    for(let i=0; i<gems.length; i++){
        gemMap.delete(gems[i]);
        gemMap.set(gems[i],i);
        if(gemMap.size===minGemsNum){
            const cand = [gemMap.values().next().value+1, i+1];
            if(answer[1]-answer[0]>cand[1]-cand[0]) answer=cand;
        }
    }
    return answer;
}

 

카카오 공식 문제 풀이 

function solution(gems) {
    let answer = [1,gems.length];
    const minGemsNum = new Set(gems).size;
    let l=0, r=0;
    const gemMap = new Map();
    gemMap.set(gems[0], 1);
    
    while(r < gems.length){
        if(gemMap.size===minGemsNum){
            if(answer[1]-answer[0]>r-l) answer=[l+1,r+1];
            gemMap.set(gems[l], gemMap.get(gems[l])-1);
            if(gemMap.get(gems[l])===0) gemMap.delete(gems[l]);
            l++;
        }else{
            r++;
            const right = gemMap.get(gems[r]);
            gemMap.set(gems[r], right ? right+1:1);
        }
    }
    return answer;
}