1046. Last Stone Weight

💡풀이

// 내 풀이
var lastStoneWeight = function (stones) {
  while (stones.length > 1) {
    stones.sort((a, b) => a - b);
    x = stones.pop();
    y = stones.pop();

    if (x >= y) stones.push(x - y);
  }
  return stones[stones.length - 1];
};

// Priority Queue
class MaxHeap {
  constructor(data = []) {
    this.data = data;
    this.comparator = (a, b) => b - a;
    this.heapify();
  }

  // O(nlog(n)). In fact, O(n)
  heapify() {
    if (this.size() < 2) return;
    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i);
    }
  }

  // O(1)
  peek() {
    if (this.size() === 0) return null;
    return this.data[0];
  }

  // O(log(n))
  offer(value) {
    this.data.push(value);
    this.bubbleUp(this.size() - 1);
  }

  // O(log(n))
  poll() {
    if (this.size() === 0) return null;
    const result = this.data[0];
    const last = this.data.pop();
    if (this.size() !== 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return result;
  }

  // O(log(n))
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = (index - 1) >> 1;
      if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  // O(log(n))
  bubbleDown(index) {
    const lastIndex = this.size() - 1;
    while (true) {
      const leftIndex = index * 2 + 1;
      const rightIndex = index * 2 + 2;
      let findIndex = index;
      if (
        leftIndex <= lastIndex &&
        this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
      ) {
        findIndex = leftIndex;
      }
      if (
        rightIndex <= lastIndex &&
        this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
      ) {
        findIndex = rightIndex;
      }
      if (index !== findIndex) {
        this.swap(index, findIndex);
        index = findIndex;
      } else {
        break;
      }
    }
  }

  // O(1)
  swap(index1, index2) {
    [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
  }

  // O(1)
  size() {
    return this.data.length;
  }
}

📝정리

이전에는 못 풀었던 문제였는데 이번엔 다시 잘 풀었던 것 같다.

그러나 스터디원들과의 얘기를 통해 Priority Queue를 사용해 푸는 방법이 가장 Optimal하다는 것을 알게 되었는데, 내가 알기로는 JS에는 Priority Queue를 직접 구현해야 하는 것으로 안다. (다른 언어는 내장되어 있는 경우가 있음)

문제 링크

https://leetcode.com/problems/last-stone-weight/

LeetCode GitHub

https://github.com/tTab1204/LeetCode/tree/main/%EC%A3%BC%EC%98%81