🖥️ 문제
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.
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.
📝 풀이
class Solution {
public List<List<Integer>> generate(int numRows) {
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int maxSum = 0;
for (int i = 0; i < nums.length; i += 2) {
maxSum += nums[i];
}
return maxSum;
}
}
이전에 풀었던 적이 있는 문제라 쉽게 풀 수 있었다. 문제의 핵심은 최소값들의 합을 최대화하는 것이다. 즉, 두개씩 짝을 지을 때 잘 지어야 한다는 것.
그래서 오름차순으로 만들고 정렬한 다음 인접한 두원소끼리 묶었다. 왜냐하면 정렬된 상태에서는 인접한 원소끼리의 차이가 가장 작이지기 때문에 두원소 중 작은 값을 더하면 그게 최대값이 된다.
👀 고찰
문제를 보고 바로 정렬 후 인접 원소를 묶는 방법이 떠올랐다는 점에서 탐욕법이 얼마나 직관적일 수 있는지를 깨달았다. 역시 중요한 건 문제를 읽고 바로 적용할 수 있는 전략을 떠올리는 능력인 것 같다.
