[LeetCode] 561. Array Partition | LIM

문제

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

Array Partition - LeetCode

 

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.

 

Example1

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

 

Example2

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

 

설명

주어진 배열에서 2개씩 묶은 후 2개 중 최솟값을 구한다. 그 최솟값들을 더했을 때의 최대값을 구하면 된다.

즉 최솟값을 더한 것들 중 최대값을 구하면 되는 문제이다. 

 

2개씩 어떻게 짝지을 것인지가 중요한 문제이다. 

 

 

푼방식

1. heapq를 이용하여 주어진 배열 중 가장 큰 값 2개를 뽑는다.

2. 그 중 최솟값을 더한다. 

3. 배열이 빌 때까지 반복한다.

 

-> 큰 값을 뽑는 이유는 최솟값을 구하는 문제이기 때문에 최솟값 중 큰 값을 찾기 위해선 큰 값 2개를 묶어야 최댓값을 구할 수 있기 때문이다. 

ex) min(1, 6) -> 1

ex) min(5, 6) -> 5

코드

import heapq
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        ans = 0
        heapq.heapify(nums)
        largest_numbers = []

        while len(nums) >= 2:
            num1 = heapq.heappop(nums)
            num2 = heapq.heappop(nums)
            ans += min(num1, num2)

        return ans

 

결과

Runtime 이 형편없었다. heapq를 사용하게 되면 계속해서 while 문을 돌면서 sorting 하는 꼴인데 사실 이 문제는 sort를 한 번만 하고 2개씩 계속해서 큰 값을 뽑은 후 그중 최솟값을 더하면 되는 것이다. 

 

 

코드 2

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        ans = 0
        nums.sort()
        for i, v in enumerate(nums):
            if i % 2 == 0:
                ans += v
        return ans

 

결과

확실히 위에 코드보다 Runtime 이 좋아진 것을 볼 수 있다. sort를 한 번만 한 후 인덱스가 짝수인 것들을 더하면 된다. 

 

 

 

참고코드

한 줄로 작성한 코드가 있었는데 결과도 매우 좋게 나왔다. 위에 내가 작성한 코드 2번을 한줄로 작성하면 이렇게 된다. 

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