[파이썬 알고리즘 인터뷰] 8. 배열 파티션1

https://github.com/onlybooks/algorithm-interview

 

1. 문제

leetcode 561. Array Partition I

 2n개의 숫자로 이루어진 정수형 배열 nums를 2개의 원소로 이루어진 n개의 부분 배열로 나눠야한다. 단, 각 배열의 최솟값의 합이 최대가 되도록 한다.

 

2. 내 풀이

 부분 배열의 최솟값들이 커지기 위해서는 같은 부분 배열의 원소 크기가 최대한 비슷해야한다. 이를 위해서는 크기 순서대로 원소들을 묶어 부분 배열을 만들어야 한다. 문제를 풀기 위해 먼저 주어진 배열을 오름차순으로 정렬했다. 그리고 짝수번째에 위치한 숫자가 각 부분배열의 최솟값이기 때문에 해당 숫자들을 모두 더해서 결과를 구했다.

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

 

3. 파이썬다운 방식

 파이썬의 슬라이싱을 사용해서 2번과 같은 내용을 한줄로 압축할 수 있다. 파이썬은 list[시작:끝:건너 뛸 숫자]와 같은 방법으로 배열을 슬라이싱 해 사용할 수 있다. 건너 뛸 숫자에 -1을 넣으면 리스트를 뒤집을 수 있다.

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