99클럽 코테 스터디 22일차 TIL

오늘의 학습 키워드

힙

과제

문제

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

• Choose the pile with the maximum number of gifts.
• If there is more than one pile with the maximum number of gifts, choose any.
• Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation:
The gifts are taken in the following way:

• In the first second, the last pile is chosen and 10 gifts are left behind.
• Then the second pile is chosen and 8 gifts are left behind.
• After that the first pile is chosen and 5 gifts are left behind.
• Finally, the last pile is chosen again and 3 gifts are left behind.
  The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation:
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile.
That is, you can't take any pile with you.
So, the total gifts remaining are 4.

Constraints:

• 1 <= gifts.length <= 103
• 1 <= gifts[i] <= 109
• 1 <= k <= 103

  풀이 과정

1. gifts 리스트와 k값을 인자로 받는 메소드를 정의합니다
2. gifts 리스트의 각 값을 음수로 변환하여 새로운 리스트 h를 만듭니다
3. 리스트 h를 힙 구조로 변환합니다
4. k번 반복합니다
5. h0의 제곱근을 구해 다시 힙에 넣습니다
6. -h[0]로 양수로 변환 → 제곱근 → 다시 음수로 변환하는 과정입니다
7. 힙의 모든 값을 더한 후 음수를 양수로 변환하여 반환합니다

제출 코드 (python)

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        h = [-v for v in gifts]
        heapify(h)
        for _ in range(k):
            heapreplace(h, -int(sqrt(-h[0])))
        return -sum(h)

오늘의 회고

• leetcode를 처음 써보는데 문제가 영어여서 당황 스러웠고 번역을 통해서 경우 풀었다
• heapify(x)라는 리스트 x를 heap으로 변환하는 함수를 처음 알았다
• heapreplace(heap, item) - heap에서 가장 작은 항목을 pop하고 반환 & 새로운 item 푸시라는 것을 알게 되었다.
  출처 :https://leetcode.com/problems/take-gifts-from-the-richest-pile/