leetcode - array-partition-i

1. 첫 시도

# Input: nums = [1,4,3,2]
# Output: 4
# Explanation: All possible pairings (ignoring the ordering of elements) are:
# 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
# 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
# 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
# So the maximum possible sum is 4.

# 제일 작은 것들끼리 우선 짝 지어야 해.
# 만약에 제일 작은 두 친구가 분산되어 있다면 그 친구들이 다 반영이 되니까,
# 전체 합이 작아질거야.

from collections import deque

def get_max_of_sum_of_mins(nums):
    sum = 0  # 전체 합 초기화.
    nums.sort()  # 작은 것들끼리 짝짓기 위해 정렬 시켜준다.

    dq = deque()  # pop()을 사용할 건데, 리스트보다는 deque 를 사용하는 것이 좋다고 했으므로

    for num in nums:  # list(nums) 를 deque 로 옮김.
        dq.append(num)

    while len(dq) != 0:  # deque 에서 두개씩 뺄건데, 더이상 남아있지 않다면 멈춤.
        max1 = dq.pop()  # 맨 오른쪽은 최댓값. pop() 으로 빼낸다.
        max2 = dq.pop()  # 또 다시 pop() 을 해준다면 두번째로 큰 값이 나온다.
        sum += max2  # 이 친구가 한 페어에서 min 이 될 것이므로  전체 합에 더해준다.

    return sum
    
nums1 = [1,4,3,2]
nums2 = [6,2,6,5,1,2]

get_max_of_sum_of_mins(nums1)  ### >> 4
get_max_of_sum_of_mins(nums2)  ### >> 9