[99클럽 코테 스터디] [leetcode] 선물이 가장 많은 꾸러미로부터 선물 가져오기

 

https://leetcode.com/problems/take-gifts-from-the-richest-pile/description/

 

당신은 다양한 꾸러미들 안의 선물들의 갯수를 나타내는 정수 배열을 받습니다.

매 초마다 당신은 아래와 같이 진행해야 합니다.

 

선물들 중 가장 최대치의 꾸러미를 선택하세요.

만약 가장 최대치인 꾸러미가 여러개라면, 아무거나 하나 선택하세요.

그 꾸러미의 선물 갯수의 제곱근의 내림(루트10 => 3.162 => 3)을 남겨두세요. 선물들의 나머지를 챙기세요.

 

K 초 후에 있을 남은 선물들의 갯수를 반환하세요.

 

입출력 예시

[25,64,9,4,100], 4

 

1회)

100 선택됨. -> 10 으로 바뀜

2회)

64 선택툄 -> 8로 바뀜

3회)

25 선택됨 -> 5로 바뀜

4회)

10 선택됨 -> 3로 바뀜

9+8+5+4+3 => 29개

 

import heapq
class Solution(object):
    numlist = []
    def pickGifts(self, gifts, k):
        numlist = list(map(lambda x: -x, gifts))
        heapq.heapify(numlist)
        for _ in range(0, k):
            mx = -numlist[0]
            heapq.heapreplace(numlist, -int(mx**(1/2.0)))
        return sum(list(map(lambda x: -x, numlist)))

 

이거 처음에 짤때 1/2로 했는데, 자꾸 계산결과가 1이 나와서 chatGPT에게 물어보니.. 이게  (1/2)가 정수 나눗셈으로 간주 될 수도 있다고 해서 GPT가 시키는 대로 분모를 실수형으로 바꿔주었다.

 

그리고 계속 정렬된 값 가지고 뭔갈 해야해서 '힙'을 사용했고, 최대힙을 쓰기 위해서 - 를 앞에 달아주었다. 문제 상에서 입력값들이 모두 양의 정수여서 위와 같이 진행했다.