[LeetCode] - 배열 파티션 I

문제) n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라 

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

Array Partition - LeetCode

---

풀이) 

 

예를 들어보자. nums = [1 , 4 ,3 , 2] 라고 할 때, n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 모든 수를 구해보자

 

min(1,4) + min(3,2) = 1 + 2 = 3 

min(1,3) + min(2,4) = 1 + 2 = 3

min(1,2) + min(3,4) = 1 + 3 = 4  

 

위 결과를 봤을 때 합이 최대가 될려면 min(a,b)가 최대가 되어야 하며, 오름차순으로 정렬 후 페어들을 만들 때 min(a,b)의 합이 최대가 된다. 이를 이용하여 풀어보자 

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

        sum = 0
        
        result = []
        #오름차순 정렬
        nums.sort()

        for n in nums :
            result.append(n)
            #만일 result가 2개일 경우 min 계산
            if len(result) == 2 :
                sum += min(result) 
                result = [] #result 초기화 

        return sum

 

위 경우를 살펴보면 항상 짝수번째에 페어의 작은 값이 위치하는 것을 알 수 있다. 리스트의 짝수들만 더해서 구해보자 

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

        result = []

        nums.sort()
        
        for i ,n in enumerate(nums) :
            if i % 2 == 0 :
                result.append(n)
        
        return sum(result)

 

위 코드를 슬라이싱을 이용하여 파이써닉하게 풀어보자 .

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

 

💡 [::2]는 2칸씩 건너뛰므로 짝수번째를 계산하는 과정과 동일하다