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

🐍 문제

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

• 입력
  [1, 4, 3, 2]
• 출력
  4

n은 2가 되며, 최대 합은 4이다.
min(1, 2) + min(3, 4) = 4
https://leetcode.com/problems/array-partition-i/

🐍 내 풀이 - 오름차순 이용

투 페어의 작은 값들의 합이 가장 커야하므로 작은 값끼리 모아둘 수 있도록 오름차순 정렬 후 순서대로 최솟값을 구하였다.

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

🐍 교재 풀이1 - 오름차순 풀이

똑같이 오름차순 정렬했지만 이유가 다르다. 뒤에서부터 가장 큰 값들을 가져오기 위해 내림차순이 필요했고 간단하게 계산하기 위해 오름차순 정렬했다.

def arrayPairSum(nums: list) -> int:
    sum = 0
    pair = []
    nums.sort()

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

    return sum

nums = [1, 4, 3, 2]
arrayPairSum(nums)  # 4

🐍 교재 풀이2 - 짝수 번째 값 계산

오름차순 정렬했기 때문에 비교하는 두 값의 최솟값은 첫번째 값일것이다, 를 이용하여 min 계산을 줄였다. 내 풀이에서 적용한다면 sum을 더할 때 min계산이 아닌 nums[i]값만 바로 더하면 된다.

def arrayPairSum(nums: list) -> int:
    sum = 0
    nums.sort()

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

    return sum

nums = [1, 4, 3, 2]
arrayPairSum(nums)  # 4

🐍 교재 풀이3 - 파이썬다운 방식

def arrayPairSum(nums: list) -> int:
    return sum(sorted(nums)[::2])

nums = [1, 4, 3, 2]
arrayPairSum(nums)  # 4