greentea31's Note

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

풀이 과정

배열을 입력 받고, 배열의 원소를 2개씩 짝지은 후, 짝에서 작은 값들의 합이 가질 수 있는 최대값을 출력하는 문제이다.

[1, 3, 2, 6, 4, 5]을 생각해보자. 1은 어떤 원소랑 짝지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 다른 수중 가장 작은 수인 2를 가져오는게 맞을 것이다.

3도 마찬가지다 1, 2가 이미 짝지어졌으니 6 4 5중 어떤 수랑 짝이 지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 남은 수중 가장 작은 4랑 묶이는게 맞을 것이다.

이런식으로 생각하다보면 그냥 배열을 오름차순 정렬한 다음에 앞에서 부터 2개씩 짝짓고, 짝의 작은 값을 다 더하면 합의 최대값이 될 것이라고 판단할 수 있다. 짝도 지을 필요가 없다. 정렬후 짝수번째 index의 원소의 합을 구해주면 된다.

소스 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        answer = 0
        nums.sort()
        for i in range(0, len(nums), 2):
            answer += nums[i]
        return answer

좀 더 효율적이고 짧은 코드

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