[파이썬 알고리즘] 배열 파티션1

배열 파티션 1

리트코드 - 배열 파티션1

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

입력
nums: [1, 4, 3, 2]
출력
4

제약 조건
1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104

n은 2가 되며, 최대 합은 4이다.
min(1, 2) + min(3, 4) = 4

---

이 문제를 간단하게 재정의하자면, 배열을 2씩 파티션하여 각각의 min값을 더한 값이 sum이라 하면,

그 sum 값이 가장 커질 수 있도록 파티션했을 때의 sum 값을 구하여라 이다.

따라서 각 파티션들의 min 값이 되도록 커야 하고, 배열을 정렬한 뒤 오름차순으로 두개씩 자르면 항상 최대 min() 페어를 유지할 수 있다.

정렬 후, 오름 차순 풀이

# arrayPairSum1.py
def arrayPairSum1(nums):
    nums.sort()
    result = 0
    length = len(nums)
    for i in range(int(length/2)):
        result += min(nums[i*2], nums[i*2 + 1])

    return result


def arrayPairSum2(nums):
    sum = 0
    pair = []
    nums.sort()

    for n in nums:
        pair.append(n)
        if len(pair) == 2:
            sum += min(pair)
            pair = []

    return sum

두 풀이는 방식은 동일하지만, 연산 수가 적은 arrayPairSum2가 더 빠른 것을 확인할 수 있다.

짝수 번째 값 계산

위의 풀이를 자세히 보면, 배열이 이미 정렬되었기 때문에, min() 연산을 해도 항상 첫 값이 결과로 sum 되는 것을 볼 수 있다.

따라서, 불필요한 min 연산을 줄일 수 있다.

# arrayPairSum2.py
def arrayPairSum(nums):
    sum = 0
    nums.sort()

    for i, n in enumerate(nums):
        if i % 2 == 0:
            sum += n

    return sum

배열 슬라이싱 활용

위의 풀이를 약간 더 정리할 수 있는데, 배열 슬라이싱을 활용하면 짧고 속도도 빠르게 풀 수 있다.

# arrayPairSum3.py
def arrayPairSum(nums):
    return sum(sorted(nums)[::2])

슬라이싱 구문 [::2]는 2칸 씩 건너 뛴다는 것을 말한다.

위의 풀이가 가장 코드가 짧으면서 성능또한 좋다.