0. 문제

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

choose an index i such that 0 <= i < nums.length,
increase your score by nums[i], and
replace nums[i] with ceil(nums[i] / 3).
Return the maximum possible score you can attain after applying exactly k operations.

The ceiling function ceil(val) is the least integer greater than or equal to val.

Example 1:

• Input: nums = [10,10,10,10,10], k = 5
• Output: 50
• Explanation: Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.

Example 2:

• Input: nums = [1,10,3,3,3], k = 3
• Output: 17
• Explanation: You can do the following operations:
  Operation 1: Select i = 1, so nums becomes [1,4,3,3,3]. Your score increases by 10.
  Operation 2: Select i = 1, so nums becomes [1,2,3,3,3]. Your score increases by 4.
  * Operation 3: Select i = 2, so nums becomes [1,2,1,3,3]. Your score increases by 3.
  The final score is 10 + 4 + 3 = 17.
  

Constraints:

1 <= nums.length, k <= 10^5

1 <= nums[i] <= 10^9

1. 초기 코드

$$ 시간복잡도=O(n log n + k log n)$$

문제점.

1. 최소/최대값 문제를 heap으로 접근하면 편하다는 것을 망각.
2. 문제에 접근할 떄, PriorityQueue 내부에서만 연산(add(), offer(), poll())이 이뤄져도 충분한데, 자꾸 int[]에 연산 결과를 반영하려함. (Array.asList() 같은 방법 사용 시도)
3. PriorityQueue를 통한 max-heap 구현 방법을 몰랐음. (new PriorityQueue<>(Comparator.reverseOrder())
4. int / 3 == int과 int / 3.0 == double의 차이를 망각. 결과적으로 문제가 제시한 ceil()의 제대로된 리턴값 생성 실패.

// 문제 해결 이후.
class Solution {
  public static long maxKelements(int[] nums, int k) {
    long score = 0;

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int num: nums)
      maxHeap.offer(num);

    for (int i = 0; i < k; i++) {
      int max = maxHeap.poll();
      score += max;
      maxHeap.offer((int) (Math.ceil(max / 3.0)));
    }
    return score;
  }
}

2. 개선 방안

1. ceil() 대신 (v + 2) / 3을 활용해 연산 단축.

class Solution {
    public long maxKelements(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int v : nums) {
            pq.offer(v);
        }
        long score = 0;
        while (k-- > 0) {
            int v = pq.poll();
            score += v;
            pq.offer((v + 2) / 3);
        }
        return score;
    }
}