[JS] [카카오인턴] 보석 쇼핑

투포인터와 MAP,SET자료형을 활용하여 해결해보았다.

 

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

프로그래머스

 

효율성 테스트가 있는 문제이기때문에 시간복잡도를 O(n)에 가깝게 풀어야 해결할 수 있을 것이라 생각했다.

문제를 접근&해결한 방식은 아래와 같다.

 

1. 배열을 순회하며 해당 인덱스의 보석은 무조건 포함된다고 생각

2. 그 보석이 포함된 기준으로 가장 짧은 길이를 계산

    2.1 만약 모든 보석이 포함되지 않았다면 길이를 계산하지 않고 map에 추가

    2.2 길이를 계산할때 map을 갱신

3. 만약 현재 계산한 거리보다 짧다면 정답 갱신

 

보석을 하나씩 추가할때 투포인터의 start에 해당되는 인덱스가 감소할일이 없기때문에 시간을 많이 아낄 수 있을 것이라 생각했다.

 

 

문제에서 제공한 예시를 푸는 방법을 보며 이해해보자.

 

 

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]

 

0. SET을 활용해 보석의 총 개수를 구한다 -> 보석은 4개

Map(0) {}

1. "DIA" -> 아직 모든 보석을 모으지 못했기에 MAP에 추가

Map(1) { 'DIA' => 1 }

2. "RUBY" -> 아직 모든 보석을 모으지 못했기에 MAP에 추가

Map(2) { 'DIA' => 1, 'RUBY' => 1 }

3. "RUBY" -> 아직 모든 보석을 모으지 못했기에 MAP에 추가

Map(2) { 'DIA' => 1, 'RUBY' => 2 }

4. "DIA" -> 아직 모든 보석을 모으지 못했기에 MAP에 추가

Map(2) { 'DIA' => 2, 'RUBY' => 2 }

5."DIA" -> 아직 모든 보석을 모으지 못했기에 MAP에 추가

Map(2) { 'DIA' => 3, 'RUBY' => 2 }

6. "EMERALD" -> 아직 모든 보석을 모으지 못했기에 MAP에 추가

Map(3) { 'DIA' => 3, 'RUBY' => 2, 'EMERALD' => 1 }

7. "SAPPHIRE" -> 아직 모든 보석을 모으지 못했기에 MAP에 추가

Map(4) { 'DIA' => 3, 'RUBY' => 2, 'EMERALD' => 1, 'SAPPHIRE' => 1 }

 

7.1 "SAPPHIRE" 보석이 추가되며 모든보석을 모았기에 start인덱스를 보석의 개수가 유지되는 최대 idx로 업데이트

start : 0 -> 2 (MAP의 "DIA"와 "RUBY"가 한개씩 줄어들었다)

Map(4) { 'DIA' => 2, 'RUBY' => 1, 'EMERALD' => 1, 'SAPPHIRE' => 1 }

 

7.2 현재 길이가 초기에 설정했던 길이보다 짧기에 정답 UPDATE

 

8. "DIA" 보석이 추가되며 start를 새로 갱신 -> "RUBY"가 한개라 start가 갱신되지 않음

Map(4) { 'DIA' => 3, 'RUBY' => 1, 'EMERALD' => 1, 'SAPPHIRE' => 1 } 2 7

 

8.1 현재길이가 정답으로 설정한 길이보다 길기에 정답을 업데이트하지 않음.

 

 

 

 

자료형들의 성질과 투포인터개념을 활용하면 나름 쉽게 해결할 수 있는 문제였다.

function solution(gems) {
    const map = new Map()
    const amount = new Set(gems).size
    
    //최소 1개의 보석을 유지하면서 가장 큰 idx를반환
    const getMinIdx = (start) => {
        while(start < gems.length){
            const curGem = gems[start]
            const gemCnt = map.get(curGem)
            
            if(gemCnt>1){
                map.set(curGem,gemCnt-1)
                start++
                continue
            }
            return start
        }
    }
    
    let start = 0
    
    let retS = 0
    let retE = gems.length
    
    for (let i = 0 ; i < gems.length ; i++){
        const gem = gems[i]
        const gemCnt = map.get(gem)
        
        if (gemCnt) map.set(gem,gemCnt+1)
        else map.set(gem,1)
        
        if (map.size<amount) continue
        
        start = getMinIdx(start)
        
        if(i-start<retE-retS){
            retE = i
            retS = start
        }
    }
    
    return([retS+1,retE+1])
    
}