[LeetCode] 561. Array Partition

 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.

• 직관적으로 생각했을 때, 각 그룹의 최솟값의 합이 최대가 되려면 작은 수부터 큰 수까지 차례대로 묶어야 할 것이다. 따라서 입력된 수열을 sort() 로 오름차순 정렬을 해준 뒤, 두 수 씩 그룹으로 묶으면 최솟값의 합이 최대가 될 것이다.

• 오름차순으로 정렬한 뒤 앞에서부터 두 수를 그룹으로 묶었으므로, 각 그룹에 대해 min()연산을 하게 되면 두 수 중 왼쪽에 있는 수가 선택될 것이고, 이는 index 로 계산하면 0부터 시작하는 짝수번호일 것이므로, 파이썬에서 제공하는 리스트 슬라이스와 sum() 을 이용하여 간단하게 구할 수 있다.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])