[자바 알고리즘 인터뷰] 7장 배열 (4) 배열 파티션 1

https://leetcode.com/problems/array-partition/description/

 

- n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라 

 

 

풀이 1) 오름 차순 풀이 

 

- 페어의 min()을 합산했을 때 최대가 되려면 결국 각각의 min()이 가급적 커야 한다는 뜻이고, 뒤에서부터 내림차순(Descending Order)으로 집어 넣으면 항상 최대 min() 페어를 유지할 수 있다. 

 

- 이 문제에서 배열의 입력값의 길이는 항상 2n개이므로 앞에서부터 오름차순(Ascending Order)으로 집어 넣어도 결과는 같을 것이다, 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자 : 박상길 <책만>

 

- 정렬된 상태에서 앞에서부터 오름차순으로 인접 엘리먼트 페어(Adjacent Element Pair)를 만들면 가장 큰 a1과 a2 페어들을 만들 수 잇고 이 페어들의 합이 곧 만들 수 있는 최대 합이 된다. 

 

1) min(1,4) + min(2,3) = 3

2) min(1,3) + min(2,4) = 3

3) min(1,2) + min(3,4) = 4

 

- 이 중 세 번째가 가장 큰 값이 되며, 앞서 설명한 대로 정렬된 상태에서 앞에서부터 오름차순으로 페어를 만든 모습이다. 

 

import java.util.*;

class Solution {
    public int arrayPairSum(int[] nums) {
        int sum = 0;
        List<Integer> pair = new ArrayList<>();
        Arrays.sort(nums);

        //앞에서 부터 오름차수능로 반복
        for(int n : nums) {
            pair.add(n);

            //페어 변수에 값이 2개 채워지면 min()을 합산하고 변수 초기화 
            if(pair.size() == 2) {
                sum +=Collections.min(pair);
                pair.clear();
            }
        }

        return sum;
    }
}

 

실행시간 : 41 밀리초 

 

 

풀이 2) 짝수번째 값 계산 

 

- 페어에 대해 일일이 min() 값을 구하지 않아도 짝수 번째 인덱스의 값을 더하면 된다. 

- 정렬된 상태에서는 짝수 번째에 항상 작은 값이 위치하기 때문이다. 

 

import java.util.*;

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

        //앞에서부터 오름차순으로 인덱스 반복
        for(int i=0; i<nums.length; i++) {
            //짝수 번째일 때 값의 합 계산
            if(i%2 == 0)
                sum+=nums[i];
        }

        return sum;
    }
}

 

실행시간 : 11 밀리초