[Greedy]99클럽 코테 스터디 21일차 TIL + 0561-array-partition

561. Array Partition

Easy

---

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

 

Example 1:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Example 2:

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

 

Constraints:

• 1 <= n <= 104
• nums.length == 2 * n
• -104 <= nums[i] <= 104

 

<내코드>

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        total = 0
        nums.sort()

        for i in range(0, len(nums) , 2):
            # total += min(nums[i : i + 2]) # 슬라이싱 + min() 이용
            total += nums[i] # 정렬 되었으므로 앞에만
            
        return total

 - 이전 과일장수문제 와 유사해서 아이디어는 금방 떠올렸음

=> 그러다보니 전체 푸는 시간은 20분이내로 끝냄

=> 이때의 반성으로 굳이 pop() 하지않고 리스트 슬라이싱을 생각해 냈다가, 그냥 앞 숫자를 그대로 들오면 되는것으로 쉽게 해결함

 

<모범사례>

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # Sort the array to ensure pairing of smallest numbers
        nums.sort()
        # Sum up the first element of each pair
        return sum(nums[i] for i in range(0, len(nums), 2))

 - 리스트 컴프리헨션으로 한줄로 한번에 처리가 가능함

- total +=  보다 sum() 이 더 용이 하게 이용이 가능함

 

<보충학습>

- 누적합을 구하는 방식에서 += 대신에 리스트 컴프리헨션과 sum() 을 생각해내기!!!