[프로그래머스][코딩테스트 고득점 Kit][Javascript] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=javascript 

프로그래머스

java 로 풀었을 땐 PriorityQueue 라이브러리를 사용해 풀어서 쉬웠는데

javascript에는 그런거 없다..

직접 heap을 구현하러 가봅시다..

 

최소 힙으로 구현하는 우선순위 큐

왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 2
부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2

index	0	1	2	3	4	5
value	1	4	8	5	2	3

 

// 최소힙
class MinHeap {
    constructor() {
        this.heap = [];
    }

    size() { return this.heap.length; }
      
    peek() { return this.heap[0]; }
  
    push(value) {
    	// 힙의 맨 뒤에 push
        this.heap.push(value);
        // value가 push 된 위치
        let index = this.heap.length - 1;

        // 오름차순 정렬
        while (
            index > 0 &&
            this.heap[index] < this.heap[Math.floor((index - 1) / 2)]
        ) {
            // Math.floor((index - 1) / 2) : index의 부모 노드
            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;
    }
}

전체 코드

class MinHeap {
    constructor() {
        this.heap = [];
    }
    size() { return this.heap.length; }
    peek() { return this.heap[0]; }
    
    push(value) {
        this.heap.push(value);
        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) {
  const minHeap = new MinHeap();

  for (const sco of scoville) {
    minHeap.push(sco);
  }

  let mixedCount = 0;

  // 힙 안에 음식이 2개 이상 있고
  // 스코빌 지수가 가장 작은 음식의 수치가 K보다 작을 때까지 반복
  while (minHeap.size() >= 2 && minHeap.peek() < K) {
    // 스코빌 지수가 가장 작은 두 음식 섞기
    const first = minHeap.pop();
    const second = minHeap.pop();
    const mixedFood = first + second * 2;
    minHeap.push(mixedFood);
    mixedCount++;
  }

  return minHeap.peek() >= K ? mixedCount : -1;
}