Python - Algorithm #29

Python Algorithm

LeetCode

2558. Take Gifts From the Richest Pile

• 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.
• Constraints
  • 1 ≤ gifts.length ≤ 10³
  • 1 ≤ gifts[i] ≤ 10⁹
  • 1 ≤ k ≤ 10³

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        # for문, sorted, pop
        for i in range(k):
            gifts = sorted(gifts)
            max_gifts = gifts.pop()
            # 가져온 가장 큰 값에 제곱근을 취해서 다시 gifts에 append
            gifts.append(int(math.sqrt(max_gifts)))
        return sum(gifts)

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        answer = 0
        for i in range(k):
            gifts.sort(reverse=True)
            gifts[0] = int(gifts[0]**0.5)
        answer = sum(gifts)
        return answer

---

3010. Divide an Array Into Subarrays With Minimum Cost I

• You are given an array of integers [nums] of length n.
• The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3.
• You need to divide [nums] into 3 disjoint contiguous subarrays.
• Return the minimum possible sum of the cost of these subarrays.
• Constraints
  • 3 ≤ n ≤ 50
  • 1 ≤ nums[i] ≤ 50

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        # 2중 for문, list slice
        answer = float('inf')
        for i in range(1, len(nums)):
            for j in range(i+1, len(nums)):
                part_one = nums[:i]
                part_two = nums[i:j]
                part_three = nums[j:]
                current_cost = part_one[0] + part_two[0] + part_three[0]
                answer = min(answer, current_cost)
        return answer

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        answer = []
        for i in range(1, len(nums)-1):
            for j in range(i+1, len(nums)):
                answer.append(nums[0] + nums[i] + nums[j])
        return min(answer)

---

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

https://leetcode.com/problems/divide-an-array-into-subarrays-with-minimum-cost-i/