Python 알고리즘 인터뷰 - 문제10. 배열 파티션 I

leetcode 561. Array Partition I - https://leetcode.com/problems/array-partition/description/

 

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

 

예제

입력

[1, 4, 3, 2]

 

출력

4

 

풀이

먼저 리스트를 정렬 시킨다. 정렬된 값을 [1, 2, 3, 4]가 된다.

min(a, b) 페어의 합의 패턴을 확인하기 위해 조합을 나열해본다. 

[1,2,3,4] 리스트의 페어의 합

 

확인 결과 (1,2),(3,4),(5,6)... 짝수 순서대로 묶었을 때 가장 큰 값이 나오는 것을 알 수 있다. 

i가 짝수일 때 min(nums[i], nums[i+1])는 항상 nums[i] 이므로 합계를 구할 때는 짝수의 값만 더하면 된다. 코드는 다음과 같다.

def arrayPairSum(self, nums):
    sum = 0
    nums.sort()
    for i in range(0, len(nums), 2):
        sum += nums[i]
    return sum

 

파이썬은 [::2] 슬라이스를 통해 짝수만을 추출할 수 있고 sum 함수로 리스트를 모두 더할 수 있다. 슬라이싱을 사용한 구현은 다음과 같다.

def arrayPairSum(self, nums):
	return sum(sorted(nums)[::2])