[LeetCode] 1877. Minimize Maximum Pair Sum in Array

문제 출처: https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/

Minimize Maximum Pair Sum in Array - LeetCode

 

문제

쌍 (a, b)의 쌍의 합은 a + b와 같다. 최대 쌍의 합은 쌍 리스트에서 쌍의 합이 가장 큰 것을 말한다.

• 예를 들어. 만약 쌍 (1, 5), (2, 3), 그리고 (4, 4)가 있다면, 최대 쌍의 합은 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8이다.

짝수 길이 n을 갖는 배열 nums가 주어지면, nums의 원소를 다음 규칙에 따라 n / 2개의 쌍으로 만든다:

• nums의 각 원소는 정확히 한 개의 쌍에 속해있다, 그리고
• 최대 쌍의 합은 최소화되어야 한다.

원소들을 최적으로 쌍을 만든 후, 최대 쌍의 합 을 반환하라.

 

예제

Input: nums = [3,5,2,3]
Output: 7

Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

Input: nums = [3,5,4,2,4,6]
Output: 8

Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

 

풀이

nums에서 아직 짝이 없는 수 중에서 가장 큰 수와 작은 수를 선택하여 쌍으로 만드는 과정을 반복하는 것으로 문제의 해답을 찾을 수 있다.

 

이러한 과정이 정말로 문제에서 원하는 결과를 출력하는지 확인하게 위해서 아래와 같이 4개의 원소로 이루어진 nums가 있다고 가정해보자.

nums = [a ,b ,c ,d], (a < b < c < d)

1. 만약 a와 b가 짝을 이룬다면, max(a+b, c+d) = c+d

2. 만약 a와 c가 짝을 이룬다면, max(a+c, b+d) = b+d

3. 만약 a와 d가 짝을 이룬다면, max(a+d, b+c) _ (현재 상황에서는 어떤게 더 크다고 판단하기 어려움)

자. 이와같은 상황에서 그 max()의 결과를 비교해보면,

- 1번 vs 2번 = c+d > b+d로 2번이 더 작은 결과를 만든다.
- 2번 vs 3번 = 아래와 같은 케이스로 3번이 더 작은 결과를 만든다.
    - 만약 3의 결과가 a+d 라면, b+d > a+d
    - 만약 3의 결과가 b+c 라면, b+d > b+c

3번 케이스에서 가장 작은 쌍의 합을 만들어 내는 것을 알 수 있다.

nums의 원소의 수를 6, 8, 10, ... 으로 확장시켜 생각해보면, 가장 큰 수와 작은 수를 쌍으로 엮는 과정을 반복하는 것으로 문제의 해답을 찾을 수 있다는 것을 알 수 있다.

 

이를 코드로 작성하면 다음과 같다.

var minPairSum = function(nums) {
    nums = nums.sort((a, b) => a - b)

    let ans = -Infinity;

    const N = nums.length;
    for (let i = 0; i < (N/2); i++) {
        ans = Math.max(ans, nums[i] + nums[N-1-i]);
    }

    return ans;
}

Github: 1877.js

opwe37/Algorithm-Study