[코테연습] 2530. Maximal Score After Applying K Operations

- 탐욕법 / 우선순위 큐 / 힙 문제

 

https://leetcode.com/problems/maximal-score-after-applying-k-operations/description/?envType=daily-question&envId=2024-10-14

 

문제 분석

• 선택한 요소를 점수에 더하기: 매번 nums[i]를 선택하고 그 값을 점수에 더함.
• 선택된 요소의 값 변경: nums[i]는 ceil(nums[i] / 3)으로 변경됨 (3으로 나눈 후 올림한 값).
• 최대 점수 찾기: 큰 수를 먼저 선택하고, 최대한 큰 값을 점수에 반영하는 것이 목표.

중요한 관찰 사항

• 큰 수를 먼저 선택: 큰 수를 먼저 골라야 나눈 뒤에도 큰 값을 유지할 수 있음.
• 최대 힙 사용: 매번 가장 큰 값을 선택해야 하므로 최대 힙(Max-Heap)을 사용해 효율적으로 큰 값을 추출.

풀이 전략

• nums 배열의 값을 최대 힙에 넣음 (음수화하여 heapq로 구현).
• k번 동안 최대 힙에서 가장 큰 값을 꺼내 점수에 더함.
• 그 값을 ceil(값 / 3)으로 갱신한 후 다시 힙에 넣음.
• 작업을 k번 반복한 후 점수를 반환.

풀이 과정

• 음수화된 nums: nums 배열을 음수로 변환하여 최소 힙(heapq)을 최대 힙처럼 사용.
• 최대 값 선택 및 점수 갱신: 최대 값을 힙에서 꺼내 점수에 더하고, 그 값을 ceil(값 / 3)으로 갱신한 후 다시 힙에 삽입.
• 반복: 이 과정을 k번 반복한 후 최종 점수를 반환.

 

> java

 

class Solution {
    public long maxKelements(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
        for (int num : nums) {
            pq.offer(num);
        }

        long sum = 0;
        for (int i = 0; i < k; i++) {
            int num = pq.poll();
            sum+=num;
            num = (int) Math.ceil((double)num/3);
            pq.offer(num);
        }

        return sum;
    }
}

 

> python

 

import heapq
import math

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        pq = []
        for num in nums :
            heapq.heappush(pq, -num)
        
        total = 0
        for i in range(k) :
            num = -heapq.heappop(pq)
            total+=num
            num = math.ceil(num/3)
            heapq.heappush(pq, -num)
        return total