Array Partition I (Pythonic way)

LeetCode의 Array Partition I 문제다.

Array Partition I - LeetCode

딱히 어려울 게 없는 문제지만 책에서 아주 인상적인 풀이를 제공했기 때문에 기록해두려고 한다. 문제 자체는 다음과 같이 간단하다.

• 2n개의 정수 목록이 주어진다.

• 정수들을 n개의 한 쌍으로 분리한다.

• 각 쌍의 최솟값의 합이 나타낼 수 있는 최댓값을 구하라.

쉽게 말해서 [1, 3, 2, 4]가 주어질 때 (1, 3), (2, 4)는 각 쌍의 최솟값이 각각 1, 2이므로 그 합은 3이다. 하지만 (1, 2), (3, 4)처럼 분리하면 각 쌍의 최솟값이 각각 1, 3이므로 그 합은 4다. 그래서 각 쌍의 최솟값의 합이 나타낼 수 있는 최댓값은 4가 된다.

 

예시만 봐도 알겠지만 결국 최솟값의 합이 최댓값이 되려면 정수들을 오름차순으로 정렬하고 두 개씩 쌍으로 묶으면 된다. 최솟값이기 때문에 한 쌍의 왼쪽에 있는 정수, 즉 홀수번째의 정수들을 합하라는 문제인데 간단한 풀이는 다음과 같다.

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

하지만 책에서 제공한 pythonic 한 풀이는 다음과 같다.

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

아주 감탄이 나오는 풀이였다. sorted 메서드를 이용해 정렬된 배열을 반환받을 수 있기 때문에 sort 메서드를 호출할 필요가 없었고 파이썬의 인덱스 슬라이싱을 활용하여 홀수번째의 정수만 남기는 모습이 인상 깊었다. 앞으로도 이런 슬라이싱을 자주 활용해야겠다.