[LeetCode] 1877. Minimize Maximum Pair Sum in Array

https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/description/

Minimize Maximum Pair Sum in Array - LeetCode

leetcode - Minimize Maximum Pair Sum in Array

문제 유형 : 정렬 / 투 포인터

문제 난이도 : Medium

 

문제

The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

• For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

• Each element of nums is in exactly one pair, and
• The maximum pair sum is minimized.

Return the minimized maximum pair sum after optimally pairing up the elements.

 

두 쌍(a, b)의 합은 a + b와 같다. 최대의 두 쌍의 합은 이 쌍들로 이루어진 리스트들 중에서 가장 큰 값이다.

n개의 정수가 주어진다. n은짝수이다. 각각의 정수로 n/2개의 가장 작은 쌍을 만들어라.

가장 큰 쌍의 합이 최소가 되게 하고, 그 값을 반환하라.

 

 

풀이

배열을 정렬해주고, 투 포인터로 양 끝을 쌍으로 시작해서 합이 더 큰 경우의 수를 만든다.

 

코드

C++

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        sort(nums.begin(), nums.end());

        int left = 0;
        int right = nums.size()-1;
        int maxPairSum = -1;

        while(left < right) {
            maxPairSum = max(maxPairSum, nums[left] + nums[right]);
            left++;
            right--;
        }

        return maxPairSum;
    }
};