[릿코드] 561번 : Array Partition I

leetcode.com/problems/array-partition-i/

Array Partition I - LeetCode

 

---

문제

2배수길이의 배열이 주어진다.

두개씩 짝지었을때 작은 값들의 최대 합을 구하라

EX) [1,4,3,2]

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 

=> 답 : 4

 

어떻게 풀까?

sort를 하고 제일 작은거 두개씩 묶는다 

-> 두 수의 차이가 작아야 버리는 숫자가 작다. 따라서 sort하고 순서대로 묶는것! 버리는 숫자를 작게하기위해 이렇게 생각하게 되었다.

 

0,2,4,... 인덱스를 더하면 끝!

 

구현 중 만난 문제/해결

IntStream을 사용해 풀어봤다.

 

구현

 

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);

        Optional<Integer> result = IntStream
                .range(0, nums.length)
                .filter(i -> i % 2 == 0)
                .mapToObj(i -> nums[i])
                .reduce((x, y) -> x + y);

        return result.get();
    }
}

 

더 나은 방식

 

구현한 방식과 방법은 같지만 intstream을 안쓴방식이다. 구현한것은 15ms가 걸렸지만 아래는 10ms가 걸린다.

 

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