[leetcode 2024/02/06] 561. Array Partition

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

maximum possible paring에 대해서 구하는 방법이다.

모든 paring을 짓고 각각의 paring의 min 값을 알아내고 그들 중 max 값을 알아내는 것은,

생각보다 간단하다.

 

만약 list 가 6, 2, 6, 5, 1, 2 라고 했을 때, sort 한다.

(1, 2,) (2, 5,) (6, 6) 이 된다.

 

2개씩 묶고 그 중 min 값을 반환하면 된다.

반환 된 min 값을 더한 것이, 답이 된다.

 

큰 수끼리 묶는 것에서 이해를 잘 할 수 있는데,

큰 수끼리 묶어야지, min(큰수, 또 다른 큰 수) 에서 하나의 큰 수라도 살아남을 수 있기 때문이다.

 

여기서, nums[i] 를 그냥 return 한 이유는,

정렬된 list이기 때문에, nums[i] 가 nums[i+1] 보다 작기 때문이다.

2. 코드

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