[leetcode 561.python] 배열 파티션 1(Array-partition 1) 풀이

https://leetcode.com/problems/array-partition/

Array Partition - LeetCode

---

문제

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

정수로 된 2n개의 배열을 받아서, n개의 쌍을 만들고, 쌍의 최솟값의 합이 최대가 되는 값을 반환하시오.

 

Example 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.

Example 2:

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

---

문제 이해

이번에도 문제만 읽고는 뭔소리야 했다가 딸려 있는 예제를 보고 이해했다 🥲

1. 일단 배열을 오름차순으로 정렬시킨 후, 짝을 지어주는 방향이 되어야겠다고 생각했다. (정렬을 하면 비슷하거나 같은 값끼리 쌍을 만들 수 있기 때문이다)

    예시) [1, 3, 4, 2] 가 있을 때,  (오름차순으로 정렬 후 짝지음) 1 2 / 3 4 → (가장 큰 최소값 더하기) 1 + 3 = 4

2. 위 예시처럼, 그렇게 한다면 첫 번째 요소가 min값일 수 밖에 없게 된다.

3. 배열에서 첫 번째 값을 모두 더한다. (=홀수번째 값만 뽑아서 더한다음 리턴하자)

---

문제 풀이

1. 입력받는 리스트를 오름차순으로 정렬한 후, 합계를 0으로 초기화한다.

nums.sort()
sum = 0

 

2. for문으로 입력받은 리스트를 반복하면서 짝수 (0, 2, ..., 2n)번째 인덱스에 해당하는 값을 1의 합계에 더한다. 반복이 종료되면 합계를 반환한다.

for i in range(0, len(nums), 2):
    sum += nums[i]

return sum

 

3. 좀 더 파이써닉한 코드 → 추가적으로 슬라이싱을 사용하면 1, 2번의 코드를 한 줄로 만들 수 있다 !!

return sum(sorted(nums)[::2])

---

문제 답

from typing import List

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        #입력받는 리스트 오름차순으로 정렬 후, 합계를 0으로 초기화
        nums.sort()
        sum = 0 

        #입력받은 리스트를 반복하면서 짝수번째 인덱스값을 sum에 더함
        for i in range(0, len(nums), 2):
            sum += nums[i]

        return sum

        #위의 다섯 줄을, 슬라이싱을 이용해 한 줄로 줄일 수 있음(n번씩 건너뛰는 방식)
        # return sum(sorted(nums)[::2])

---

마치며

그룹 애너그램 문제보다는 이해하기 훨씬 쉬웠다. 파이썬 문법이 흥미로워지고 있다!