[프로그래머스/JS] Lv2. 더 맵게 (힙 자료구조, 우선순위 큐 구현)

문제

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

프로그래머스

---

풀이

우선 순위 큐를 구현해야하는 문제이다. 자바에서는 라이브러리를 불러오면 쉽게 해결되지만, 자바스크립트에서는 직접 구현을 해야한다.

 

우선 순위 큐를 어떻게 구현할 수 있을까? 우선 순위 큐는 힙 자료 구조를 알면 쉽게 접근해볼 수 있다.

 

힙은 완전 이진 트리의 일종이다. 특징은 부모 노도의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리이다.

 

여기서 힙의 종류는 두 가지가 있다.

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

어려운 것은 아니고, 값이 큰 게 우선인가 작은 것이 우선인가로 나누어볼 수 있는 것이다.

 

 

 

그럼 이 힙을 어떻게 구현해야할까? 답은 배열로 구현할 수 있다.

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

 힙의 루트부터 아래로 인덱스를 매겨보면, 왼쪽 자식의 인덱스는 부모의 인덱스의 *2이고 오른쪽 자식 인덱스는 부모 인덱스 *2 +1 이라는 것을 확인할 수 있다. 반대로 부모의 인덱스는 자식의 인덱스/2 한 값이다. 이것을 배열에 넣으면 힙을 간접적으로 표현할 수 있는 것이다.

 

 

 힙에 대해서는 정리가 된 것 같다. 이제 그럼 우선 순위를 어떻게 나타낼 수 있을까? 새로운 요소를 삽입하고 삭제할 때, 그에 알맞게 정렬해주면 우선 순위를 유지할 수가 있다.

 

 

삽입하는 경우를 그림으로 쉽게 살펴보자.

 

 

 

삽입한 요소를 부모와 비교하며, 조건에 맞지 않을 때까지, 교환하는 과정을 거치는 것을 알 수 있다.

 

 

이것을 자바 스크립트 코드로 나타낸 것은 아래와 같다. 참고로 최소 힙을 구현한 것이다.

 

주석을 통해 코드를 설명했다.

 

class MinHeap{
    constructor(){
        this.heap = []; //배열을 선언한다.
    }
    push(item){ //삽입
        this.heap.push(item); //배열의 가장 마지막에 값을 삽입한다.
        let index = this.heap.length-1;

		//삽입한 값이 루트가 되거나, 부모값보다 작은 경우가 아닐 때까지 계속해서 스왑한다.
        while(index > 0 
              && this.heap[index] < this.heap[Math.floor((index-1)/2)])
            {
                const temp = this.heap[index];
                this.heap[index] = this.heap[Math.floor((index-1)/2)];
                this.heap[Math.floor((index-1)/2)] = temp;
                
                index = Math.floor((index-1)/2);
            }
    }
    
    pop(){ //최상단의 루트 값을 빼낸다. 빼내고 나서 재정렬을 해주어야한다.
        if(this.heap.length===0) return null;
        if(this.heap.length===1) return this.heap.pop(); //만약 하나밖에 없다면 오버헤드 줄이기
        
        const minValue = this.heap[0]; //반환해야할 값
        this.heap[0] = this.heap.pop();
        
        let index = 0;
        while(index*2+1 < this.heap.length){ //자식 인덱스가 전체 배열 길이보다 작다면 반복
            //교환할 자식 인덱스를 선택한다.
            let minChildIndex = index * 2 + 2 < this.heap.length // 오른쪽 자식이 힙의 길이보다 작은지를 체크한다.
                && this.heap[index * 2 + 2] < this.heap[index * 2 + 1] // 오른쪽자식 노드값이 왼쪽자식보다 작은지 확인한다.
                ? index * 2 + 2 조건에 부합하면 오른쪽
                : index * 2 + 1; 아니라면 왼쪽을 선택한다.
                 
            if(this.heap[index] < this.heap[minChildIndex]){ //만약 자식이 인덱스보다 크다면 거기서 멈춘다.
                break;
            }
        	//스왑
            const temp = this.heap[index];
            this.heap[index] = this.heap[minChildIndex];
            this.heap[minChildIndex] = temp;
            
            index = minChildIndex;
        }
        return minValue;
    }
}

 

 

 

 

 

 

이를 이용해 문제를 해결한 것은 아래와 같다.

---

소스 코드

function solution(scoville, K) {
    var answer = 0;
    
    let heap = new MinHeap();
    
    for(let i =0;i<scoville.length;i++){
        heap.push(scoville[i]);
    }
    
    let count = 0;
    while(heap.peek()<K){
        let food1 = heap.pop();
        let food2 = heap.pop();
        
        let newFood = food1+food2*2;
        heap.push(newFood);
        count++;
    }
    answer = heap.peek()>=K ? count: -1;
    return answer;
}

class MinHeap{
    constructor(){
        this.heap = [];
    }
    
    size(){
        return this.heap.length;
    }
    
    push(item){
        this.heap.push(item);
        let index = this.heap.length-1;

        while(index > 0 
              && this.heap[index] < this.heap[Math.floor((index-1)/2)])
            {
                const temp = this.heap[index];
                this.heap[index] = this.heap[Math.floor((index-1)/2)];
                this.heap[Math.floor((index-1)/2)] = temp;
                
                index = Math.floor((index-1)/2);
            }
    }
    
    pop(){
        if(this.heap.length===0) return null;
        if(this.heap.length===1) return this.heap.pop();
        
        const minValue = this.heap[0];
        this.heap[0] = this.heap.pop();
        
        let index = 0;
        while(index*2+1 < this.heap.length){
            
            let minChildIndex = index * 2 + 2<this.heap.length 
            && this.heap[index*2+2] < this.heap[index*2+1]?index*2+2:index*2+1;
            
            if(this.heap[index] < this.heap[minChildIndex]){
                break;
            }
            
            const temp = this.heap[index];
            this.heap[index] = this.heap[minChildIndex];
            this.heap[minChildIndex] = temp;
            
            index = minChildIndex;
        }
        return minValue;
    }
    
    peek(){
        return this.heap[0];
    }
}

 

 

 

 

참고자료

https://velog.io/@eldoradodo/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-JavaScript-%EB%8D%94-%EB%A7%B5%EA%B2%8C

https://velog.io/@eldoradodo/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-JavaScript-%EB%8D%94-%EB%A7%B5%EA%B2%8C

https://mingmeng030.tistory.com/293