[LEET CODE] 561. Array Partition I

# Problem

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. Constraints: 1 <= n <= 104 nums.length == 2 * n -104 <= nums[i] <= 104

 

# My Answer

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

 

# Solution 1 - 오름차순 풀이

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

        for n in nums:
            # 앞에서 부터 오름차순으로 페어를 만들어 합 계산
            pair.append(n)
            if len(pair) == 2:
                sum += min(pair)
                pair = []

        return sum

오름차순으로 인접 요소 페어 만들기

 

# Solution 2  - 짝수 번째 값 계산

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

        for i, n in enumerate(nums):
            # 짝수 번째 값의 합 계산
            if i % 2 == 0:
                sum += n

        return sum

정렬된 상태에서는 짝수번째에 항상 작은 값 위치

 

# Solution 3 - 파이썬다운 방식

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

solution2를 슬라이싱 구문 활용하여 짝수 번째 계산

가장 성능이 좋음 ( 슬라이싱 활용)