Leetcode 561: 배열 파티션 1

 

n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.


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

// 입력 예제
[1,4,3,2]

// 출력 예제
4

//min(1,2) + min(3,4) = 4

 

 

 

풀이

 

1. 내림차순 풀이

 

페어의 min()의 합이 최대가 되려면 결국 min()이 최대한 커야 한다는 뜻이기 땜누에

내림차순으로 정렬한 뒤에 페어를 만들면 최대 min()페어를 유지할 수 있다. 

 

def arrayPairSum(self, nums: List[int]) -> int:
    # 내림 차순 정렬
    nums.sort(reverse=True)
    sum = 0

    # 큰 것끼리 묶어서 그 중 작은걸 골라야 가장 큰 값을 구할 수 있다.
    # [4,3,2,1]에서 min(4,3), min(2,1)
    for i in range(0, len(nums)-1, 2):
        sum += min(nums[i], nums[i+1])
    return sum