파이썬 알고리즘 인터뷰 10번 배열 파티션 (리트코드 561)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

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.

2n 개의 원소를 가진 정수 배열을 2개씩 묶어 그 중 작은 값들의 합의 최대를 구하여라

Solution

이 문제는 단순하게 정렬한 뒤에 두개씩 묶으면 그 조합이 최대가 되는 조합임을 찾으면 끝이다.

풀이 1

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        result = 0
        for i in sorted(nums)[::2]:
            result += i
        return result

)

풀이 2 - 파이썬다운 방식 (해설 3)

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

Reference

파이썬 알고리즘 인터뷰 p190 ~ 192