[LeetCode] Array-partition-i

문제

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.

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.

 

풀이

문제에서 2n이라 표현했으니 2개씩 끊을 수 있을 것이다. 그리고 나서 정렬의 특성을 이용해보자. [1,4,3,2]로 생각해보자면 다음과 같이 정렬되었을 거고

[1,2,3,4] // sort

 2개씩 끊은 다음 최소값을 뽑아서 더해주면 문제에서 요구하는 답을 도출해 낼 수 있을 것 같다

result =0

1. result +=  [1,2] -> min(1)   
2. result +=  [3,4] -> min(3)

 

풀이 시도

class Solution:    
    def arrayPairSum(self, nums: List[int]) -> int:
        result = 0
        nums.sort()

        for k, v in enumerate(nums):
            if k % 2 != 0:
                result += min(nums[k - 1:k + 1])
        return result

2개씩 잘라서 enumerate로 잘라서 최소값을 result에 더해주는 방식으로 잘랐다. 하지만 k가 증가하는 값을 기준으로 -1과 +1을 해서 범위를 뽑아내기 때문에 뭔가 직관적이지 못한 코드이지 않나라는 생각이 든다.

def arrayPairSum(self, nums: List[int]) -> int:
    result = 0
    depth = 2
    nums.sort()

    for i in range(0, len(nums), depth):
        result += min(nums[i:i + depth])

좀 더 개선해보고자 해서 위와 같이 해봤다. depth를 2로 세워두고 slicing으로 배열의 범위(length: 2씩)를 뽑은 다음 더해주는 방식이다.

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

다른 방법은 뭐가 있을까해서 조사해봤는데 pythonice하게 위와 같이 푸는 방법도 있었다.

 

후기

사실 처음엔 이것저것 생각해보다가 안 풀려서 풀이보고 정리한 내용이다. 알고리즘의 길은 멀고도 험하다.