[JAVA 문제 풀이] 387. Minimum Difference in Sums After Removal of Elements

[요소 제거 후 합계의 최소 차이]

Jul 18, 2025

[JAVA 문제 풀이] 387. Minimum Difference in Sums After Removal of Elements

Contents

Minimum Difference in Sums After Removal of Elements - LeetCode

Can you solve this real interview question? Minimum Difference in Sums After Removal of Elements - You are given a 0-indexed integer array nums consisting of 3 * n elements. You are allowed to remove any subsequence of elements of size exactly n from nums. The remaining 2 * n elements will be divided into two equal parts: * The first n elements belonging to the first part and their sum is sumfirst. * The next n elements belonging to the second part and their sum is sumsecond. The difference in sums of the two parts is denoted as sumfirst - sumsecond. * For example, if sumfirst = 3 and sumsecond = 2, their difference is 1. * Similarly, if sumfirst = 2 and sumsecond = 3, their difference is -1. Return the minimum difference possible between the sums of the two parts after the removal of n elements. Example 1: Input: nums = [3,1,2] Output: -1 Explanation: Here, nums has 3 elements, so n = 1. Thus we have to remove 1 element from nums and divide the array into two equal parts. - If we remove nums[0] = 3, the array will be [1,2]. The difference in sums of the two parts will be 1 - 2 = -1. - If we remove nums[1] = 1, the array will be [3,2]. The difference in sums of the two parts will be 3 - 2 = 1. - If we remove nums[2] = 2, the array will be [3,1]. The difference in sums of the two parts will be 3 - 1 = 2. The minimum difference between sums of the two parts is min(-1,1,2) = -1. Example 2: Input: nums = [7,9,5,8,1,3] Output: 1 Explanation: Here n = 2. So we must remove 2 elements and divide the remaining array into two parts containing two elements each. If we remove nums[2] = 5 and nums[3] = 8, the resultant array will be [7,9,1,3]. The difference in sums will be (7+9) - (1+3) = 12. To obtain the minimum difference, we should remove nums[1] = 9 and nums[4] = 1. The resultant array becomes [7,5,8,3]. The difference in sums of the two parts is (7+5) - (8+3) = 1. It can be shown that it is not possible to obtain a difference smaller than 1. Constraints: * nums.length == 3 * n * 1 <= n <= 105 * 1 <= nums[i] <= 105

https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/description/


'3 * n'개의 원소로 구성된 0-인덱스 정수 배열 'nums'가 주어집니다.

'nums'에서 크기가 정확히 'n'인 요소의 하위 시퀀스를 제거할 수 있습니다.
나머지 '2 * n' 요소는 두 개의 동일한 부분으로 나뉩니다:

* 첫 번째 부분에 속하는 첫 번째 'n'개의 요소와 그 합은 'sumfirst'입니다.
* 두 번째 부분에 속하는 다음 'n'개의 요소와 그 합은 'sumsecond'입니다.

두 부분의 합 차이는 'sumfirst - sumsecond'로 표시됩니다.

* 예를 들어, 'sumfirst = 3'과 'sumsecond = 2'의 차이는 '1'입니다.
* 마찬가지로, 만약 'sumfirst = 2'와 'sumsecond = 3'이라면, 그들의 차이는 '-1'입니다.

n개의 요소를 제거한 후 두 부분의 합 사이의 가능한 최소 차이를 반환합니다.

제약 조건:
* nums.length == 3 * n
* 1 <= n <= 105
* 1 <= nums [i] <= 105

내가 작성한 코드


import java.util.*;

public class Solution {
    public long minimumDifference(int[] nums) {
        int n = nums.length / 3;
        int len = nums.length;
        long[] leftSum = new long[len];
        long[] rightSum = new long[len];

        // 앞쪽 n개의 합 중 가장 작은 합 유지
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        long sum = 0;

        for (int i = 0; i < 2 * n; i++) {
            sum += nums[i];
            q.offer(nums[i]);

            if (q.size() > n) {
                sum -= q.poll();
            }

            if (q.size() == n) {
                leftSum[i] = sum;
            }
        }

        // 뒤쪽 n개의 합 중 가장 큰 합 유지
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        sum = 0;

        for (int i = len - 1; i >= n; i--) {
            sum += nums[i];
            minHeap.offer(nums[i]);

            if (minHeap.size() > n) {
                sum -= minHeap.poll();
            }

            if (minHeap.size() == n) {
                rightSum[i] = sum;
            }
        }

        // 최소 차이 계산
        long answer = Long.MAX_VALUE;

        for (int i = n - 1; i < 2 * n; i++) {
            if (rightSum[i + 1] != 0) {
                // 왼쪽 n개와 오른쪽 n개가 겹치지 않도록하고 최소 차이 구하기
                long diff = leftSum[i] - rightSum[i + 1]; 
                answer = Math.min(answer, diff);
            }
        }

        return answer;
    }
}