[프로그래머스] 2020카카오 인턴십 - 보석 쇼핑

오늘 푼 문제

 

3. 보석 쇼핑 / Lv.3 / 시간: 100분(시간초과)

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

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

1. 틀린 코드

function solution(gems) {
    var answer = [];
    let list = [...new Set(gems)];
    let hash = gems.reduce((acc,cur)=> {
        acc[cur] = {config:1,index:null};
        return acc;
    } ,{})
    // console.log(list,hash);
    
    let len = list.length;
    let s = 0;
    let pos = 0;
    while(len){
        let cur = gems[pos];
        if(hash[cur].config){
            hash[cur].config = 0;
            len--;
        }else{
            if(cur===list[s]){
                s++;
            }
        }
        hash[cur].index = pos;
        pos++;
    }
    
    let min=hash[list[s]].index;
    // console.log('min',min,'s',s)
    for(let i=0;i<s;i++){
        let temp = hash[list[i]].index;
        if(min>temp) min = temp;
    }
    
    let last = gems[--pos];
    answer = [min+1,hash[last].index+1];
    return answer;
}

 

[풀이]

100분이나 걸렸는데 저게 최선이었다. (8.9점임....)

결국 다른 사람의 풀이를 찾아보고 이해함.

출처 : velog.io/@diddnjs02/코딩테스트프로그래머스-보석-쇼핑

[코딩테스트]프로그래머스 - 보석 쇼핑

function solution(gems) {
    var answer = [];
    let num = [...new Set(gems)].length;
    let gemMap = new Map();
    let list = [];
    gems.forEach((v,i)=>{
        if(gemMap.has(v)) gemMap.delete(v);
        gemMap.set(v,i);
        if(gemMap.size===num) list.push([gemMap.values().next().value,i])
    });
    list.sort((a,b)=>{
        if((a[1]-a[0]) === (b[1]-b[0])) return a[0]-b[0];
        else return (a[1]-a[0]) - (b[1]-b[0])
    })
    answer = [list[0][0]+1,list[0][1]+1];
    return answer;
}

 

 

이 풀이의 핵심은

1. js 의 Map 자료형 사용.

2. 모든 보석을 포함하는 가능한 모든 구간을 구한 뒤 구간들 중 최소 범위를 가지는 구간을 출력한다.

 

[Map]

Map 자료형은 순서가 저장되는 버전의 hash와 같다고 보면 된다. 기존의 보석이 재등장 할 경우 순서를 파악하기 위해 일반 객체 자료형과 배열을 같이 사용했는데 그럴 필요가 없다. 

자주 쓰지 않아서 생소한 자료형이었는데 알아두면 좋을 듯.