문제
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1: Input: [1,4,3,2]
Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4). Note: n is a positive integer, which is in the range of [1, 10000]. All the integers in the array will be in the range of [-10000, 10000].
풀이
배열의 원소를 쌍을 짓고 그 쌍의 최소값의 합이 최대가 되어야 하는 문제이다.
생각의 흐름
쌍의 최소값의 합이 최대가 되어야 한다는것을 곰곰히 생각해보았다.
그렇다면, 배열 내의 원소중 버려야 하는 원소는 없고 어떤 원소든 무조건 선택이 되어야 한다.
그러면 작은 원소를 큰 원소와 맵핑 시켰을때 큰 손해를 보게 된다. 작은 원소는 그 다음 작은 원소와 맵핑 시켜야 가장 이득을 보면서 쌍을 지을수있다.
따라서, 배열을 먼저 정렬해야 하고 순서대로 쌍을 지으며 쌍 중 앞의 원소를 선택하면 가장 손해를 덜보면서 최대값을 구할 수 있다.
/**
* @param {number[]} nums
* @return {number}
*/
var arrayPairSum = function(nums) {
nums = nums.sort((a, b) => a - b);
let result = 0;
for (let i = 0; i < nums.length; i += 2) {
result += nums[i];
}
return result;
};결과
