1. 문제

문제링크 : https://leetcode.com/problems/array-partition

2. 풀이

2.1. 짝수 번째 원소의 합

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

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

합은 쌍의 최솟값들을 더해서 만들어지기 때문에 합이 최대가 되기 위해선 쌍을 만들 때 최대한 큰 값끼리 묶어야 한다. 큰 값끼리 묶이기 위해선 배열을 정렬한 후 첫 번째 원소와 두 번째 원소를 묶고, 세 번째 원소와 네 번째 원소를 묶는 방식으로 쌍을 만들어야 한다. 정렬된 순으로 쌍을 만들면 결국 큰 값끼리 묶이게 된다. 이런 식으로 쌍을 만들었을 때 배열의 모든 짝수 번째 원소는 모든 쌍들의 최솟값이 된다. 따라서 모든 짝수 번째 원소를 더하면 최종적으로 구하려 하는 값이 된다. 이 과정을 코드로 구현하면, 처음엔 nums를 정렬한다. 이후 for문에서 nums의 모든 짝수 번째 원소를 result에 더하고 반복이 끝나면 result를 반환한다. 정렬은 $O(n\log n)$의 시간 복잡도를 갖고 for문의 시간 복잡도는 $O(n)$이므로 이 풀이의 시간 복잡도는 $O(n\log n)$이 된다.

2.2. 한 줄 풀이

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

짝수 번째 원소의 합을 더하는 방식은 같지만 슬라이싱과 sum 함수를 활용하여 코드를 간결하게 만들었다.