2530.js

/** ------------------------------------------------------------------------------
 * 
 * 2530. Maximal Score After Applying K Operations
 * Topics: Greedy, Heap
 * https://leetcode.com/problems/maximal-score-after-applying-k-operations/?envType=daily-question&envId=2024-10-14
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// var maxKelements = function (nums, k) {
//   let start = 0
//   let answer = 0

//   while (start < k) {
//     let max = Math.max(...nums)
//     answer += max
//     const i = nums.findIndex((v) => v === max)
//     nums[i] = Math.ceil(nums[i] / 3)

//     start++
//   }
//   return answer
// }

/**
 * leetcode 내장 라이브러리
 */
var maxKelements = function (nums, k, res = 0) {
  const pq = new MaxPriorityQueue()
  for (let num of nums) {
    pq.enqueue(num)
  }
  while (k) {
    const el = pq.dequeue().element
    res += el
    pq.enqueue(Math.ceil(el / 3))
    k--
  }
  return res
}

/**
 * 커스텀 Heap
 */
var maxKelements = function (nums, k) {
  const heap = getHeap(nums)
  let answer = 0

  for (let i = 0; i < k; i++) {
    answer += heap.update()
  }

  return answer
}

const getHeap = (arr) => {
  function siftDown(start = 0) {
    let curr = start
    while (true) {
      const left = curr * 2 + 1
      const right = left + 1
      let next = curr

      if (left < arr.length && arr[left] > arr[next]) next = left
      if (right < arr.length && arr[right] > arr[next]) next = right

      if (next !== curr) {
        ;[arr[curr], arr[next]] = [arr[next], arr[curr]]
      } else break
    }
  }

  function update() {
    const res = arr[0]
    arr[0] = Math.ceil(arr[0] / 3)
    siftDown()
    return res
  }

  const start = Math.floor(arr.length / 2) - 1
  for (let i = start; i >= 0; i -= 1) siftDown(i)

  return { update }
}

/**
 * 세 개의 포인터
 * 내림차순 정렬로 nums[0]은 항상 가장 큰 값이 됨
 */
function maxKelements(nums, k) {
  let result = 0
  nums.sort((a, b) => b - a)

  if (k === 1) {
    return nums[0]
  }

  for (let i = 0, index = 0; i < k; i++) {
    let [a, b, c] = [nums[index], nums[index + 1], nums[0]]
    if (a >= b && a >= c) {
      result += a
      nums[index] = Math.ceil(a / 3)
    } else if (b > a && b > c) {
      index++
      result += b
      nums[index] = Math.ceil(b / 3)
    } else {
      index = 0
      result += c
      nums[0] = Math.ceil(c / 3)
      nums.sort((a, b) => b - a)
    }
  }

  return result
}