[Javascript] 프로그래머스 보석 쇼핑

문제

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

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

 

 

풀이 과정

결론부터 말하면 이 문제는 단순 이중 for문으로 해결할 수 없다. 만약 이중 for문으로 해결하려고 한다면 정확성은 다 통과되지만 효율성에서 시간 초과될 것이다. 맨 처음 내가 작성한 코드는 아래와 같다. 

function solution(gems) {
    let result = [], minLen = 100000;
    let unique = [...new Set(gems)];
    let gemLen = gems.length, uniLen = unique.length;
    if(uniLen === 1){
        return [1, 1];
    }else if(gemLen === uniLen){
        return [1, gemLen];
    }
    for(let i = 0; i <= gemLen - uniLen; i++){
        if([...new Set(gems.slice(i))].length !== uniLen) break;
        let answer = [], values = [];
        values.push(gems[i]);
        answer.push(i);
        for(let j = i + 1; j < gemLen; j++){
            if(!values.includes(gems[j])){
                values.push(gems[j]);
                answer.push(j);
                let anLen = answer.length;
                if(anLen === uniLen){
                    if(answer[anLen - 1] - answer[0] < minLen){
                        minLen = answer[anLen - 1] - answer[0];
                        result[0] = answer[0] + 1;
                        result[1] = answer[anLen - 1] + 1;
                    }
                    break;
                }
            }
        }
    }
    return result;
}

정확성은 맞지만 효율적이지 않은 코드이다. 효율성을 증가시키기 위해 객체가 아닌 배열만 사용하고 리터럴 방식만 사용하려고 노력했으나 결과는 똑같았다. 그래서 찾아본 게 '슬라이딩 윈도우 알고리즘'이다.

 

슬라이딩 윈도우 알고리즘이란?

윈도우를 한 칸 옮기면, n - 1칸은 겹친다는 게 슬라이딩 윈도우의 기본 아이디어. 이를 적용해 수정한 코드는 아래와 같다.

function solution(gems) {
    let result = [], minLen = 100000;
    let checkMap = new Map();
    // 중복되는 보석 제거
    let kind = new Set(gems);
    let curr = new Map(), s = 0;
  
	// 보석 진열장 처음부터 끝까지 순환
    for(let i = 0; i < gems.length; i++){
        // 만약 checkMap에 특정 보석이 없다면
        if(!checkMap.has(gems[i])){
            // 특정 보석을 key로, 빈 배열을 value로 생성해주고
            checkMap.set(gems[i], []);
        }
        // 특정 보석을 key로 갖는 배열에 인덱스를 추가해준다
        checkMap.get(gems[i]).push(i);
        // caseArr의 key에 인덱스를, value에는 보석 이름을 추가해준다
        caseArr.set(i, gems[i]);
        // 만약 checkMap에 모든 보석의 종류가 추가되어있다면
        if(kind.size === checkMap.size){
            // checkMap에서 gems의 0번째부터 1씩 증가시키며, 
            // value 길이가 1이 될 때까지 배열의 요소를 삭제한다
            while(checkMap.get(gems[s]).length > 1){
                checkMap.get(gems[s]).shift();
                // caseArr에서도 0부터 1씩 증가시키며 key를 삭제한다
                caseArr.delete(s);
                s++;
            }
            // caseArr의 크기가 minLen보다 작다면
            if(caseArr.size < minLen){
                // minLen을 caseArr.size로 변경시켜 최소 길이를 바꿔주고
                minLen = caseArr.size;
                // result에 시작점 + 1, 시작점 + 최소 길이를 저장한다
                result[0] = s + 1;
                result[1] = s + minLen;
            }
            // 슬라이딩 윈도우 알고리즘에 맞춰 시작점을 한 칸 증가시켜주고,
            s++;
            // checkMap에서 이전 시작점에서 보석에 대한 value중, 먼저 저장된 인덱스를 제거한다
            checkMap.get(gems[s - 1]).shift();
            // 제거한 결과, 보석의 value값인 배열이 비었다면
            if(checkMap.get(gems[s - 1]).length === 0){
            	// checkMap에서 해당 보석을 삭제한다
                checkMap.delete(gems[s - 1]);
            }
            // caseArr에서도 이전 시작점을 제거한다
            caseArr.delete(s - 1);
        }
    }

    return result;
}

Map 객체를 사용한 이유는 배열을 사용하면 매번 인덱스를 확인해야되지만, Map 객체는 key를 알면 값을 찾을 때 시간이 단축되기 때문이다. 또한 Map 객체 타입이 가진 여러가지 특징 중 1) size 속성으로 객체 크기를 쉽게 알 수 있고, 2) 객체에서 키 - 값을 삭제하거나 추가할 경우 일반 Object 객체보다 성능이 좋기 때문에 이를 잘 활용하면 시간 단축을 할 수 있다.

Map

 

 

테스트 케이스 추가