TIL _ 탐욕법(Greedy) _ 0813 _ TUE

오늘의 문제 _  561. Array Partition(LeetCode)

나의 풀이

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;
    }
}

 

나의 회고

미리 20001 크기의 배열 arr을 생성한 후, 배열 nums의 값을 인덱스 삼아 배열 arr값을 초기화했다.

그랬더니 별도로 정렬을 수행하지 않아도 빠르게 값 얻어낼 수 있었음!

 

덧

좀 더 간결한 코드

public int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int sum = 0;

    for (int i = 0; i < nums.length - 1; i += 2) {
        sum += Math.min(nums[i], nums[i + 1]);
    }
    return sum;
}