더 맵게 (opens in a new tab)

문제 해결 방법

minHeap(최소힙)의 root(peek) 값이 K 이상이 될 때까지 mix를 반복한다
- mix는 가장 맵지 않은 음식 + (두 번째로 맵지 않은 음식 * 2)이다
enq시, 원소를 삽입한 후 heapify를 진행한다
- curIdx 값이 0보다 크고, 부모 노드 값이 현재 노드의 값보다 클 경우, heapify를 진행한다
deq시, root 값을 제거한 후, root 자리에 마지막 원소를 삽입한다
- curIdx * 2 + 1 값이 최소 힙의 사이즈보다 작을 경우, heapify를 진행한다
- 이때, 현재 원소 값이 자식 원소 값보다 작은 경우, heapify 반복을 중단한다
mix의 최소 횟수를 리턴하고, 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 리턴한다

오답노트

deq() 함수 내에서 배열이 비었는지를 체크하는 로직이 존재하는지
음식이 하나가 남았고 그 음식의 스코빌 지수가 K 미만인 경우를 고려했는지

코드

class MinHeap {
  #arr;
 
  constructor(els) {
    this.#arr = els ?? [];
  }
 
  enq(el) {
    this.#arr.push(el);
 
    let curIdx = this.#arr.length - 1;
    let parIdx = Math.floor((curIdx - 1) / 2);
 
    while (curIdx > 0 && this.#arr[parIdx] > this.#arr[curIdx]) {
      this._swap(curIdx, parIdx);
      curIdx = parIdx;
      parIdx = Math.floor((curIdx - 1) / 2);
    }
  }
 
  deq() {
    if (this.#arr.length === 0) return null;
    if (this.#arr.length === 1) return this.#arr.pop();
 
    const originRoot = this.#arr[0];
    this.#arr[0] = this.#arr.pop();
    let curIdx = 0;
 
    while (curIdx * 2 + 1 < this.#arr.length) {
      let childIdx =
        curIdx * 2 + 2 < this.#arr.length &&
        this.#arr[curIdx * 2 + 2] < this.#arr[curIdx * 2 + 1]
          ? curIdx * 2 + 2
          : curIdx * 2 + 1;
 
      if (this.#arr[curIdx] < this.#arr[childIdx]) {
        break;
      }
 
      this._swap(curIdx, childIdx);
      curIdx = childIdx;
    }
    return originRoot;
  }
 
  _swap(a, b) {
    const tmp = this.#arr[a];
    this.#arr[a] = this.#arr[b];
    this.#arr[b] = tmp;
  }
 
  get size() {
    return this.#arr.length;
  }
 
  get peek() {
    return this.#arr[0];
  }
}
 
function solution(scoville, K) {
  const minHeap = new MinHeap();
  let cnt = 0;
 
  for (let s of scoville) {
    minHeap.enq(s);
  }
 
  while (minHeap.size >= 2 && minHeap.peek < K) {
    const mixed = minHeap.deq() + minHeap.deq() * 2;
    minHeap.enq(mixed);
    cnt += 1;
  }
 
  return minHeap.peek >= K ? cnt : -1;
}

실패했던 코드

1차

deq() 함수 내에서 배열이 비었는지를 체크하는 로직이 존재하지 않았음

class MinHeap {
  #arr;
 
  constructor(els) {
    this.#arr = els ?? [];
  }
 
  enq(el) {
    let curIdx = this.#arr.length - 1;
    let parIdx = Math.floor((curIdx - 1) / 2);
 
    this.#arr.push(el);
 
    while (curIdx > 0 && this.#arr[parIdx] > this.#arr[curIdx]) {
      this._swap(curIdx, parIdx);
      curIdx = parIdx;
    }
  }
 
  deq() {
    const originRoot = this.#arr[0];
 
    this.#arr[0] = this.#arr.pop();
    let curIdx = 0;
 
    while (curIdx * 2 + 1 < this.#arr.length) {
      let childIdx =
        curIdx * 2 + 2 < this.#arr.length &&
        this.#arr[curIdx * 2 + 2] < this.#arr[curIdx * 2 + 1]
          ? curIdx * 2 + 2
          : curIdx * 2 + 1;
 
      if (this.#arr[curIdx] < this.#arr[childIdx]) {
        break;
      }
 
      this._swap(curIdx, childIdx);
      curIdx = childIdx;
    }
    return originRoot;
  }
 
  _swap(a, b) {
    const tmp = this.#arr[a];
    this.#arr[a] = this.#arr[b];
    this.#arr[b] = tmp;
  }
 
  get size() {
    return this.#arr.length;
  }
 
  get peek() {
    return this.#arr[0];
  }
}
 
function solution(scoville, K) {
  const minHeap = new MinHeap();
  let cnt = 0;
 
  for (let s of scoville) {
    minHeap.enq(s);
  }
 
  while (minHeap.size >= 2 && minHeap.peek < K) {
    const mixed = minHeap.deq() + minHeap.deq() * 2;
    minHeap.enq(mixed);
    cnt += 1;
  }
  return minHeap.peek >= K ? cnt : -1;
}

2차

음식이 하나가 남았고 그 음식의 스코빌 지수가 K 미만인 경우를 고려하지 않음

class MinHeap {
  #arr;
 
  constructor(els) {
    this.#arr = els ?? [];
  }
 
  enq(el) {
    this.#arr.push(el);
 
    let curIdx = this.#arr.length - 1;
    let parIdx = Math.floor((curIdx - 1) / 2);
 
    while (curIdx > 0 && this.#arr[parIdx] > this.#arr[curIdx]) {
      this._swap(curIdx, parIdx);
      curIdx = parIdx;
    }
  }
 
  deq() {
    if (this.#arr.length === 0) return null; // 1차 에러코드 개선
    if (this.#arr.length === 1) return this.#arr.pop(); // 1차 에러코드 개선
 
    const originRoot = this.#arr[0];
    this.#arr[0] = this.#arr.pop();
    let curIdx = 0;
 
    while (curIdx * 2 + 1 < this.#arr.length) {
      let childIdx =
        curIdx * 2 + 2 < this.#arr.length &&
        this.#arr[curIdx * 2 + 2] < this.#arr[curIdx * 2 + 1]
          ? curIdx * 2 + 2
          : curIdx * 2 + 1;
 
      if (this.#arr[curIdx] < this.#arr[childIdx]) {
        break;
      }
 
      this._swap(curIdx, childIdx);
      curIdx = childIdx;
    }
    return originRoot;
  }
 
  _swap(a, b) {
    const tmp = this.#arr[a];
    this.#arr[a] = this.#arr[b];
    this.#arr[b] = tmp;
  }
 
  get size() {
    return this.#arr.length;
  }
 
  get peek() {
    return this.#arr[0];
  }
}
 
function solution(scoville, K) {
  const minHeap = new MinHeap();
  let cnt = 0;
 
  for (let s of scoville) {
    minHeap.enq(s);
  }
 
  while (minHeap.size >= 2 && minHeap.peek < K) {
    const mixed = minHeap.deq() + minHeap.deq() * 2;
    minHeap.enq(mixed);
    cnt += 1;
  }
 
  return minHeap.peek >= K ? cnt : -1;
}

04 Tree and Priority Queue 42584