[leetcode/python] 561번 Array Partition

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

 

문제 요약 : 배열에서 두 개씩 짝을 지었을 때의 최솟값으로 만들 수 있는 최대 합을 구하라

최솟값끼리 더한 것이 최대 합이 되려면 작은 것끼리 짝을 맞추면 된다.

 

로직은 다음과 같다.

1. 오름차순으로 정렬한다

2. 두개씩 짝지었을 때 짝수번째가 작은 값이 되기 때문에 이를 합산해 준다.

 

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        for i, n in enumerate(sorted(nums)):
            if i % 2 == 0:
                sum += n
        return sum

시간복잡도는 O(n)이다