[파이썬 알고리즘] 7장 배열 - 배열 파티션 (array partition)

https://leetcode.com/problems/array-partition-i/

Array Partition I - LeetCode

 

<문제>

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.

 

<예시>

Input: nums = [1,4,3,2] Output: 4

 

---

min의 합이 어떻게 하면 maximized될까를 고민해보면 쉽게 풀 수 있는 문제였다.

1. 정렬을 수행한다
   1. 예시 > [a1, a2, a3, a4, ..., a99, a100]
2. 홀수번째 값들을 선택한다
   1. 정렬을 수행하면 가장 큰 값을 제외한 나머지 값 중 maximum은 두 번째로 큰 수이다. (a99)
   2. 따라서 상위 2개의 쌍을 묶고 (a99, a100)
   3. 나머지 데이터 중 가장 큰 값을 제외한 나머지 값 중 maximum은 나머지 중 두 번째로 큰 수이다. (a97)
   4. 따라서 상위 2개의 쌍을 묶고 ... (a97, a98)
   5. 이런 식으로 반복한다.
   6. 이러면 (a1, a2), (a3, a4), ... , (a99, a100) 이렇게 쌍이 지어지고
      각 쌍의 min의 합은 정렬 후 홀수번째 위치한 데이터의 합과 동일하게 된다.

def solution_1(nums: List[int]) -> int:
    # 1. 정렬
    nums.sort()
    # 2. 홀수번째 값의 합(짝수 index)
    return sum(nums[::2])