[Programmers] 보석 쇼핑 문제 - (javascript)

문제 이름 :  보석 쇼핑

---

 

<<< 문제 내용 >>>

---

 

function solution(gems) {
    let answer = [];
    
    const gemCount = new Set(gems).size;
    let gemMap = new Map();
    gems.map((el, i)=>{
        gemMap.delete(el);
        gemMap.set(el, i);
        
        if(gemMap.size === gemCount){
            answer.push([gemMap.values().next().value+1, i+1]);
        }
    })
    
    answer.sort((a, b)=>{
        if(a[0]-a[1] < b[0]-b[1]) return 1;
        else if(a[0]-a[1] === b[0]-b[1]){
            return a[0]-b[0];
        }else return -1;
    });
    
    return answer[0];
}

* 레벨 3 다웠다.. 처음 문제를 보고 투포인터로 보석 갯수만큼 찾으면,

left을 올리면서 최적의 수를 찾으면 되겠다 싶었다.

찾고 나서는 Math.min, max를 이용하여 범위를 출력하게끔 했다.

 

그러고 맞이한 정답률은 처참했고, 효율성 또한 2개를 제외한 아무것도 통과하지 못했다.

 

고민을 하던 도중 반례는 깨달았다. [B, B, B, C, D, C, A, B] 가 있을 때

원래 생각했던 알고리즘 이라면, [B, C, D, C, A]를 투포인터로 최적이라고 찾게 되는데

실상 답은 [D, C, A, B] 가 나와야 한다. 때문에, 투포인터 만으론 해결할 수 없는 문제라고 여겼다.

 

결국, 구글링을 통해 정답을 배웠는데 코드를 리뷰하고 느낀 점은 와.. Map의 특성을 정말 잘 살린 방법이구나

싶었다.

 

Map은 delete를 통해 지우고 새로 작성하게 되면, 삽입 순서대로 기록이 된다. <- 핵심

이를 통해 최소값, 최대값을 구하는 함수를 쓰면서 시간낭비를 할 필요가 없게된다.

 

또 앞의 반례처럼, 앞에서 발견되는게 아닌 뒤에서도 발견되는 보석조합도 사이즈가 같을때마다 push 해주어서

이 보석 조합들을 구간의 길이가 짧은 순으로 정렬하고, 구간의 길이가 같은 경우는 구간의 시작점끼리 비교해 오름차순으로 정렬하면 된다.

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.