[Leetcode] 561번 - 배열 파티션

1. 문제 파악

1. 문제 링크: https://leetcode.com/problems/array-partition/
2. 문제 정의: 주어진 배열에서 두개의 요소를 쌍을 지은 모든 경우의 수에서, 각 쌍의 최소값을 모두 더한 최대값을 구해라.
3. 문제의 제약 파악 (입력값 크기, 상수 조건)
   • 1 <= nums.length <= 10000: 시간복잡도가 O(NlogN) 이내여야 통과하는데 안전하다.

---

2. 문제 풀이

1. 브루트 포스로 문제 풀이 도출

브루트 포스로 풀수 있는 방법을 모르겠었다. 짧은 시간내에 배열의 요소의 모든 조합 쌍을 묶는 코드가 떠오르지 않았다. 따라서 부르트 포스로 문제 풀이가 떠오르지 않아므로 창의적인 아이디어가 필요할거라고 생각되었다.

 

2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?

문제를 돌파할 창의적인 아이디어를 떠올리기 위해서 생각이 나지 않았다. 그치만 해당 문제 설명에서 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 내용을 보고 아이디어를 유추할수는있었다.

 

긱 쌍에서 최소깂의 합이 최대가 되야하므로, 쌍에서 값의 차이가 적을수록 최대값이 커진다. 따라서 배열을 오름차순 정렬후에 쌍에서 첫번째 요소들을 모두 더한값이 최대값이다. 또한 정렬은 O(NlogN)이 걸리므로 시간내에 문제를 풀수있다.

1. 배열을 오름 차순으로 정렬한다.
2. 인덱스를 2씩 증가시키며 요소값을 모두 더한다.
3. 최대값을 반환한다.

 

3. 입출력 케이스 도출 및 문제 풀이 도출 확인

• 일반 케이스:
  • Ex1
    • Input: nums = [1,4,3,2]
    • Output: 4
  • Ex2
    • Input: nums = [6,2,6,5,1,2]
    • Output: 9
• 엣지 케이스: 엣지 케이스는 따로 없는 것으로 판단

위의 핵심 문제 풀이 로직에서 입출력 케이스에 문제될 특히 사항은 없으므로 넘어간다.

 

4. 코드 구현

핵심 문제 풀이 로직을 코드로 구현하면 다음과 같다.

class Solution {
    public int arrayPairSum(int[] nums) {
        int n = nums.length;
        int max = 0;

        // 1. 배열을 오름 차순으로 정렬한다.
        Arrays.sort(nums);

        // 2. 인덱스를 2씩 증가시키며 요소값을 모두 더한다.
        for (int i = 0; i < n; i+=2) {
            max += nums[i];
        } 

        // 3. 최대값 반환
        return max;
    }
}

 

5. 복잡도

• 시간 복잡도
  • 배열 정렬: O(NlogN)
  • 배열 순회: O(N)
  • 최종 시간복잡도: O(NlogN)와 O(N) 중에서 높은 시간 복잡도 = O(NlogN)
• 공간 복잡도
  • 추가 공간은 최대값을 저장하기 때문에 O(1)이다.