풀이_LC561.md

🎃 561. Array Partition I

• Date : 2021.10.24(일)
• Time : 20분

Problem

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

Constraints

• 1 <= n <= 10^4
• nums.length == 2 * n
• -10^4 <= nums[i] <= 10^4

Example

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

풀이

    def arrayPairSum(self, nums: List[int]) -> int:
        nums = sorted(nums)
        return sum(nums[i] for i in range(0, len(nums), 2))
    
        

: 개인적으로 이런 문제 좋아하지 않는데.. 그래도 한번 풀어보았다. 일단 여기서 제시하는 문제는 두개씩 숫자를 잘라서 최소값을 다 더했을 때 가장 크게 나오는 조합의 최대값을 찾아라! 인데.. sort를 통해 쉽게 풀 수 있는 문제이다. 최소값의 조합이 최대값이 나오게 하려면 어떻게 해야할까?의 생각만 해결하면 풀 수 있는 문제다. 최소값의 조합이 최대값이 나오려면 최대한 작은수는 작은수끼리 큰 수는 큰수끼리 붙여야한다. 1,3조합에서 1이 살아남고 3이 죽는거보다는 2,4 조합에서 2가 살아남고 3이 죽는게 이득이니깐!! 그래서 작은순으로 정렬을 해서 2개씩 자른 다음 최소값을 다 더해주면 되는것이다!