1962. Remove Stones to Minimize the Total

1962. Remove Stones to Minimize the Total

Remove Stones to Minimize the Total - LeetCode

piles라는 스톤을 모아둔 리스트가 주어지고

k라는 int가 주어져서 k만큼 piles 스톤들을 뺄 수 있다. 예를들어

Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.

piles = [5,4,9] 여기서 9를 → 9 - floor(piles[i] / 2) 이렇게 할 수 있다.

문제는 that you can apply the operation on the same pile more than once.

하나의 스톤에 여러 작업을 할 수 있다는 거다 그래서 정렬한다음 제일 큰값만 작업해주자 해서

코드를 짰다

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        lst_piles = sorted(piles, reverse=True)
        for i in range(0, k):
            pile = lst_piles[0] // 2
            lst_piles[0] -= pile
            lst_piles = sorted(lst_piles, reverse=True)
        return sum(lst_piles)

근데 웬걸 타임 리밋트가 걸리네..

그럴줄 알았다… n log n 인데 n 값이 9만정도되면 타임리밋이 걸리더라

어쨌건 매번 작업할 때 큰 수를 구해야 하는데

그러면 결국 어떤 수가 크냐를 알아야 함

그러면 항상 큰수가 가장 먼저오는 자료구조를 찾아야 했고 그게 heap메모리임

이진데이터트리를 사용하면 되는데 python에서는 heap을 역순으로 정리하는건 없어서

들어오는 데이터 값을 -로 변경해서 정렬

import heapq
from typing import List

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        heap = []
        for item in piles:
            heapq.heappush(heap, -item)
        for _ in range(k):
            pile = heapq.heappop(heap)
            pile = pile * -1
            pile -= pile//2
            heapq.heappush(heap, -pile)
        return -sum(heap)

특이한 점은

5//2 == 2 인데

-5//2 == -3 이다.

이점 주의해서 풀어야 할 듯