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() 을 생각해내기!!!
'문제풀이 > 일일연습문제' 카테고리의 다른 글
[Graph]99클럽 코테 스터디 23일차 TIL + 2121-find-if-path-exists-in-graph (0) | 2024.08.16 |
---|---|
[Graph]99클럽 코테 스터디 22일차 TIL + 1916-find-center-of-star-graph (0) | 2024.08.15 |
[DP]99클럽 코테 스터디 20일차 TIL + 0119-pascals-triangle-ii (0) | 2024.08.13 |
[Greedy]99클럽 코테 스터디 19일차 TIL + 프로그래머스/1/135808. 과일 장수 (0) | 2024.08.09 |
[DFS/BFS]99클럽 코테 스터디 18일차 TIL + 0933-increasing-order-search-tree (0) | 2024.08.08 |