[leetcode] Array Partition I

Array Partition I

풀이

[1,4,3,2] 가 있을 때 정렬하면 [1,2/3,4]가 된다. 여기서 1+3을 하면 최댓값이 된다. 다른 예로 [6,2,6,5,1,2]를 정렬한 [1,2/2,5/6,6]에서 1+2+6을 하면 된다.

이 풀이법은 sorted가 최대 시간복잡도로 O(N)이 된다.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums = sorted(nums)
        sum = 0
        for index in range(0, len(nums), 2):
            sum += nums[index]
        return sum

처음에 생각한 접근법

조합으로 몇 개를 뽑아서 다 돌려봐야 하나, 최댓값부터 작은 값으로 내려가면서 계산을 해봐야 하나 별 생각을 다 했다.

참고 자료

Nick White