[프로그래머스/더 맵게] - JS로 힙 직접 구현해보기

문제 설명

---

프로그래머스

 

시간 복잡도

---

힙을 사용하지 않고, 코드를 구현했었는데, 효율성까지 통과해야하는 문제였기 때문에 힙을 사용해서 구현을 해야만 효율성을 모두 통과할 수 있었다. 

 

처음에는 힙을 사용하지 않고 배열을 매번 정렬했었기에 nlogn의 시간복잡도가 걸렸지만, 힙을 사용함으로써 logn으로 시간복잡도를 줄일 수 있었다. 

 

 

알고리즘 설계

---

처음 작성한 코드는 아래와 같다. 

function solution(scoville, K) {
    let answer = 0; // 섞어야 하는 최소 횟수
    
    // 모든 값이 K 이상인지 확인하기
    while(true) {
        // 순차정렬
        scoville = scoville.sort((a, b) => a - b);
        // 섞은 음식의 스코빌 지수
        let newScoville = scoville[0] + (scoville[1] * 2);
        // 첫 번째 값과 두 번째 값 제거
        scoville.splice(0, 2);
        // 계산한 값 맨 앞에 추가
        scoville.unshift(newScoville);
        answer++;
        
        // 모든 값이 K 이상인 경우
        if(scoville.filter((el) => el >= K).length === scoville.length) break;
        // 배열의 길이가 1 이하인 경우 종료
        if(scoville.length <= 1) break;
    }
    
    // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우: -1
    for (let el of scoville) {
        if (el < K) {
            answer = -1;
            break;
        }
    }   
    
    return answer;
}

 

틀린 부분

---

1. 순차정렬이 아닌 우선순위 큐 사용하기

배열을 매번 정렬하는 대신 힙을 사용하면 nlogn의 시간복잡도를 logn으로 줄일 수 있다.

 

2. 조건 확인 최적화하기

배열 전체를 순회하지 않고, 섞은 결과로 생긴 새로운 음식의 스코빌 지수가 K이상인 경우 나머지도 K이상임이 보장된다. 

 

다른 풀이

---

class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
    return this.heap;
  }

  getParentIdx(childIdx) {
    return Math.floor((childIdx - 1) / 2);
  }

  getLeftChildIdx(parentIdx) {
    return parentIdx * 2 + 1;
  }

  getRightChildIdx(parentIdx) {
    return parentIdx * 2 + 2;
  }

  heapPop() {
    const heapSize = this.size();
    if (!heapSize) return null;
    if (heapSize === 1) return this.heap.pop();

    const value = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return value;
  }

  heapPush(value) {
    this.heap.push(value);
    this.bubbleUp();

    return this.heap;
  }

  bubbleUp() {
    let child = this.size() - 1;
    let parent = this.getParentIdx(child);

    while (this.heap[child] < this.heap[parent]) {
      this.swap(child, parent);
      child = parent;
      parent = this.getParentIdx(parent);
    }
  }

  bubbleDown() {
    let parent = 0;
    let leftChild = this.getLeftChildIdx(parent);
    let rightChild = this.getRightChildIdx(parent);

    while (
      (leftChild <= this.size() - 1 && this.heap[leftChild] < this.heap[parent]) ||
      (rightChild <= this.size() - 1 && this.heap[rightChild] < this.heap[parent])
    ) {
      if (rightChild <= this.size() - 1 && this.heap[leftChild] > this.heap[rightChild]) {
        this.swap(parent, rightChild);
        parent = rightChild;
      } else {
        this.swap(parent, leftChild);
        parent = leftChild;
      }
      leftChild = this.getLeftChildIdx(parent);
      rightChild = this.getRightChildIdx(parent);
    }
  }
}

function solution(scoville, K) {
  let count = 0;
  const heap = new MinHeap();
  scoville.forEach((el) => heap.heapPush(el));

  while (heap.heap[0] < K && heap.size() > 1) {
    count++;
    heap.heapPush(heap.heapPop() + heap.heapPop() * 2);
  }
  return heap.heap[0] >= K ? count : -1;
}

 

 

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖