[Java] LeetCode 561 : Array Partition I

LeetCode # 561

---

 

 

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.

 

Constraints :

• 1 <= n <= 10⁴
• nums.length == 2 * n
• -10⁴ <= nums[i] <= 10⁴

---

Solution #1 (10ms)

class Solution {
    public int arrayPairSum(int[] nums) {
        int result = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i=i+2){
            result+=nums[i];
        }
        return result;
    }
}

 

Result #1

💡 오름차순 정렬 후, 짝수번째 인덱스를 더한다.

오름차순으로 정렬하면 두 개씩 쌍을 이루었을 때, 짝수번째 인덱스가 최솟값임을 알 수 있다. 직관적이지만 효율은 좋지 않다.

---

Solution #2 (3ms)

class Solution {
    public int arrayPairSum(int[] nums) {
        int[] arr = new int[20001];
        int lim = 10000, sum = 0;
        for (int n : nums) arr[n + lim]++;

        int k = 0;

        for (int i = 0; i < nums.length; i = i + 2) {
            while (arr[k] == 0) k++;

            sum += k - lim;
            
            if (arr[k] == 1) {
                k++;
                while (arr[k] == 0) k++;
                arr[k]--;
            } else {
                arr[k] -= 2;
            }
        }

        return sum;
    }
}

 

Result #2

💡 Constraints 을 이용하여 20001 크기의 배열을 생성한다.

20001 크기의 배열 arr 을 생성한 후, 배열 nums 의 값을 인덱스 삼아 배열 arr 값을 초기화해준다. 별도로 정렬을 수행하지 않아도 되므로 빠르게 결과값을 얻을 수 있다.

 

 

---

 

More Algorithm!

 

👇👇

 

github.com/ggujangi/ggu.leet-code

ggujangi/ggu.leet-code

 

 

 

 

출처 : leetCode