[Algorithm] 더 맵게 | 요람일지

문제설명

더 맵게는 작은 순으로 정렬된 매운 음식들의 스코빌 지수가 K보다 작을 때 가장 작은 음식 2개를 섞어 K 이상으로 만든 후 섞은 횟수를 반환하는 문제이다.

문제해결

1차: 정렬 & Queue

Queue 배열에서 가장 작은 요소 2개를 꺼내 mix(Queue[0] + Queue[1] * 2)한 후 push하고 queue를 모두 검사하기 전 mix와 K 이상이면 count를 반환하는 방식으로 접근했다. 결과는 효율성 테스트 실패

function solution(scoville, K) {
  let count = 0;
  const queue = [];

  for (const s of scoville) {
    queue.push(s);
  }

  queue.sort((a, b) => a - b);
  while (queue.length - 1) {
    const first = queue.shift();
    const second = queue.shift();
    const mixed = first + second * 2;
    queue.push(mixed);
    queue.sort((a, b) => a - b);
    count++;

    if (queue[0] >= K) return count;
  }
  return queue[0] >= K ? count : -1;
}

2차: Class로 Heap 구현

### Heap

Heap은 이진트리를 그리며 부모노드가 자식보다 작거나 같은 경우를 만들어 내는 자료 구조이다.

자바는 메서드로 구현되어 있는데 자바스크립트는 없어서 직접 만들어야 한다.

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

  size() {
    return this.heap.length;
  }
    
  push(value) {
    this.heap.push(value);
    let idx = this.heap.length - 1;

    while (
      idx > 0 &&
      this.heap[idx] < this.heap[Math.floor((idx - 1) / 2)]
    ) {
      const temp = this.heap[idx];
      this.heap[idx] = this.heap[Math.floor((idx - 1) / 2)];
      this.heap[Math.floor((idx - 1) / 2)] = temp;
      idx = Math.floor((idx - 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 idx = 0;

    while (idx * 2 + 1 < this.heap.length) {
      let minIdx = idx * 2 + 2 < this.heap.length && this.heap[idx * 2 + 2] < this.heap[idx * 2 + 1] ? idx * 2 + 2 : idx * 2 + 1;

      if (this.heap[idx] < this.heap[minIdx]) {
        break;
      }

      const temp = this.heap[idx];
      this.heap[idx] = this.heap[minIdx];
      this.heap[minIdx] = temp;
      idx = minIdx;
    }

    return minValue;
  }

  peek() {
    return this.heap[0];
  }
}

function solution(scoville, K) {
  const minHeap = new MinHeap();

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

  let count = 0;

  while (minHeap.size() >= 2 && minHeap.peek() < K) {
    const first = minHeap.pop();
    const second = minHeap.pop();
    const mixed = first + second * 2;
    minHeap.push(mixed);
    count++;
  }

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

push, pop, peek 메서드의 시간 복잡도는 모두 O(log N)으로 전체 시간 복잡도는 O(N log N)으로 앞서 구현한 코드의 시간복잡도 O(N^2 log N)보다 빠르다.