배열 분할

✏️오늘의 문제

💡나의 풀이

---

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

문제의 핵심

문제의 목표는 주어진 배열을 두 개의 그룹으로 나누어 각 그룹의 최소값의 합을 최대화하는 것입니다. 배열의 길이는 항상 짝수이므로, 각 그룹에는 n/2개의 요소가 포함됩니다.

접근 방식

1. 정렬의 필요성

   • 배열을 정렬하면, 인접한 두 숫자가 서로 가까운 값이 됩니다. 이로 인해 각 그룹의 최소값이 최적화될 수 있습니다. 예를 들어, 배열이 [1, 4, 3, 2]일 경우 정렬하면 [1, 2, 3, 4]가 되며, (1, 2)와 (3, 4)로 나눌 수 있습니다. 이 때 최소값의 합은 1 + 3 = 4가 됩니다.

2. 짝수 인덱스 선택

   • 정렬 후 짝수 인덱스의 요소만 선택하는 이유는, 정렬된 배열에서 인접한 두 요소 중 첫 번째 요소가 항상 더 작은 값이기 때문입니다. 즉, (nums[0], nums[1]), (nums[2], nums[3])와 같은 쌍을 만들었을 때, 첫 번째 요소가 항상 두 번째 요소보다 작거나 같으므로, 짝수 인덱스의 요소를 선택하는 것이 최선의 선택입니다.

3. 시간 복잡도

   • 이 알고리즘의 시간 복잡도는 O(n log n)입니다. 이는 배열을 정렬하는 데 걸리는 시간입니다. 그 후, 배열을 한 번 순회하는 O(n) 시간이 추가되므로, 전체적으로 효율적인 방법입니다.

💡더 효율적인 코드

주어진 코드는 LeetCode 561번 문제 "Array Partition I"를 해결하는 방법 중 하나로, 배열의 최소값의 합을 최대화하기 위해 빈도 기반의 접근 방식을 사용합니다. 아래에 코드의 각 부분을 자세히 설명하겠습니다.

코드 설명

class Solution {
    public int arrayPairSum(int[] nums) {
        int max = Integer.MIN_VALUE; // 배열의 최대값을 찾기 위한 변수
        int min = Integer.MAX_VALUE; // 배열의 최소값을 찾기 위한 변수

        // 배열의 최대값과 최소값을 찾음
        for (int num : nums) {
            max = Math.max(num, max); // 최대값 업데이트
            min = Math.min(num, min); // 최소값 업데이트
        }

        // 빈도 배열 초기화
        int[] counts = new int[max - min + 1];

        // 각 숫자의 빈도 계산
        for (int num : nums) {
            counts[num - min]++; // 해당 숫자의 빈도 증가
        }

        int res = 0; // 결과 변수, 최소값의 합을 저장
        int idx = 0; // 빈도 배열의 인덱스

        // 쌍을 만들면서 최소값의 합 계산
        for (int i = 0; i < nums.length / 2; i++) {
            // 다음 사용 가능한 최소값 찾기
            while (counts[idx] == 0) {
                idx++; // 인덱스를 증가시켜 빈도 배열에서 0이 아닌 값을 찾음
            }
            res += idx; // 현재 인덱스의 값을 결과에 추가
            counts[idx]--; // 사용한 숫자의 빈도 감소

            // 다음 사용 가능한 두 번째 최소값 찾기
            while (counts[idx] == 0) {
                idx++; // 다음 인덱스로 이동
            }
            counts[idx]--; // 두 번째 숫자의 빈도 감소
        }

        // 최소값의 합에 최소값 * (배열 길이 / 2)을 추가하여 결과 반환
        return res + nums.length / 2 * min;
    }
}

코드의 주요 단계

1. 최대값과 최소값 찾기

   • max와 min 변수를 초기화하여 배열의 최대값과 최소값을 찾습니다. 이를 통해 빈도 배열을 생성할 때 필요한 범위를 결정합니다.

2. 빈도 배열 생성

   • int[] counts = new int[max - min + 1]; : 최대값과 최소값의 차이를 기반으로 빈도 배열을 초기화합니다. 이 배열은 각 숫자의 출현 횟수를 기록합니다.
   • 두 번째 for 루프에서 각 숫자의 빈도를 증가시킵니다. counts[num - min]++는 해당 숫자의 빈도를 기록합니다.

3. 최소값의 합 계산

   • for (int i = 0; i < nums.length / 2; i++) : 배열의 길이의 절반만큼 반복합니다. 이는 쌍을 만들기 위해 필요한 반복 횟수입니다.
   • while (counts[idx] == 0) : 빈도 배열에서 0이 아닌 값을 찾기 위해 인덱스를 증가시킵니다. 이 과정에서 최소값을 찾습니다.
   • res += idx; : 현재 인덱스의 값을 결과에 추가합니다.
   • 두 번째 while 루프에서 다음 최소값을 찾고 빈도를 감소시킵니다.

4. 결과 반환

   • return res + nums.length / 2 * min; : 계산된 최소값의 합에 최소값을 쌍의 수 만큼 곱하여 최종 결과를 반환합니다.