LeetCode | Easy | 561. Array Partition

LeetCode | Easy | 561. Array Partition

Problems

• 📘 Src: LeetCode
• 🗂️ Cat: Greedy

Description

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

Examples

nums	Output
[1, 4, 3, 2]	4
[6, 2, 6, 5, 1, 2]	9

Solutionse

• ⏳ TC: O(n log n)
• 💾 SC: O(1)

import java.util.*;

class Solution {

    public int arrayPairSum(int[] nums) {
        // 배열이 2개의 요소만 있는 경우, 두 수 중 작은 값을 반환
        if (nums.length == 2) return Math.min(nums[0], nums[1]);

        // 배열을 정렬
        Arrays.sort(nums);
        int sum = 0;

        // 홀수 번째 요소들의 합을 계산
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }

        return sum;
    }
}

Approaches

이 문제는 정렬을 사용하여 간단하게 해결할 수 있습니다. 주어진 배열을 정렬한 후, 홀수 번째 요소들을 합산하면 최대 합을 얻을 수 있습니다. 이는 각 쌍의 최소값을 최대화하는 데 효과적입니다.

정렬된 배열에서 각 두 번째 요소는 해당 쌍에서 더 작은 값이 됩니다. 예를 들어, 배열이 [4, 2, 1, 3]라면, 정렬된 후에는 [1, 2, 3, 4]가 되고, 여기서 홀수 번째인 1과 3을 선택합니다. 이는 각 쌍의 최소값을 최대화하기 위해, 더 작은 값을 선택하는 전략입니다.

이 과정을 단계별로 살펴보면 다음과 같습니다:

• 배열을 오름차순으로 정렬합니다. 이는 각 쌍의 최소값을 최대화하기 위해 필요한 준비 단계입니다. 정렬 알고리즘은 O(n log n)의 시간 복잡도를 가집니다.
• 정렬된 배열에서 모든 홀수 번째 요소들을 합산합니다. 이는 각 쌍의 첫 번째 요소가 가장 작은 값이 되도록 보장합니다.
• 최종 합을 반환합니다.

이 알고리즘은 매우 효율적이며, 배열을 정렬한 후 한 번의 순회를 통해 해결할 수 있습니다. 따라서 시간 복잡도는 O(n log n)이며, 추가적인 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.