99클럽 코테 스터디 23일차 TIL Array Partition

# 오늘의 학습 키워드 

탐욕법(Greedy)

 

# 오늘의 문제 

https://leetcode.com/problems/array-partition/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.

 

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 <= 104
• nums.length == 2 * n
• -104 <= nums[i] <= 104

 

# 나의 풀이방식 

import java.util.Arrays.*;
import java.util.*;

class Solution {
    public int arrayPairSum(int[] nums) {
        int result = 0;

        // 배열 요소중에서 작은 수는 작은수끼리, 큰 수는 큰수끼리 더해야 합이 최대값이 되므로 
        // 배열을 정렬
        Arrays.sort(nums);


        // 2개의 수를 더해서 최소값을 더한 후 return
        int prev = 0; 
        int num = 0;
        for(int i=0; i<nums.length; i++){
            if(i%2 == 0){
                prev = nums[i];
            }else{
                num = nums[i];
                result = result + Math.min(prev,num);
                prev = 0; 
                num = 0;
            }
        }

        return result;
        
    }
}

 

# 오늘의 회고 

요근래 탐욕법 문제를 많이 풀다보니 조금씩 감이 오는것 같다. 근시안적인 최적의 방법을 찾아서 푸는거!