[leetcode]1818. Minimum Absolute Sum Difference

문제

You are given two positive integer arrays nums1 and nums2, both of length n.

The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).

You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.

Return the minimum absolute sum difference after replacing at most one element in the array nums1. Since the answer may be large, return it modulo 109 + 7.

|x| is defined as:

x if x >= 0, or
-x if x < 0.

예시

• Example 1:

  	- Input: nums1 = [1,7,5], nums2 = [2,3,5]
  	- Output: 3
  	- Explanation: There are two possible optimal solutions:
  		- Replace the second element with the first: [1,7,5] => [1,1,5], or
  		- Replace the second element with the third: [1,7,5] => [1,5,5].
  		Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.

• Example 2:

  	- Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
  	- Output: 0
  	- Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an absolute sum difference of 0.

• Example 3:

  	- Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
  	- Output: 20
  	- Explanation: Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7]. This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

제한사항

n == nums1.length
n == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 105

풀이1

var minAbsoluteSumDiff = function(nums1, nums2) {
   let absoluteSumDiff = 0
   const length = nums1.length
   
    let maxAdjustment
    for (let i = 0; i < length; i++) {
        const actualDiff = Math.abs(nums1[i]-nums2[i])
        if (actualDiff === 0) continue;
        
        absoluteSumDiff += actualDiff
        if (maxAdjustment && maxAdjustment >= actualDiff) continue
        for (let j = 0; j < length; j++) {
            if (i !== j) {
                const temp = Math.abs(nums1[j]-nums2[i])
                if (temp < actualDiff) {
                    const adjustment = actualDiff - temp
                    if (maxAdjustment === undefined || maxAdjustment < adjustment)
                        maxAdjustment = adjustment
                }
            }
        }
    }
    const result = maxAdjustment === undefined ? absoluteSumDiff : absoluteSumDiff - maxAdjustment
    return (result) % (10**9 + 7)
};

nums1에서 값을 다른 값으로 하나만 바꿔서 각 값의 차이의 절댓값의 합을

풀이2

var minAbsoluteSumDiff = function(nums1, nums2) {
    const n = nums1.length;
    const array=[];
    for(let i=0; i<n; i++){
        array.push(Math.abs(nums1[i]- nums2[i]));
    }
    
    
    const diffArray=[];
    for(let i=0 ;i<n;i++){
        const item = array[i];
        let diff = -1;
        
        for(let j=0;j<n;j++){
            const tempDiff =item - Math.abs(nums2[i] - nums1[j])
            diff=diff<tempDiff?tempDiff:diff
        }
        diffArray.push(diff);
    }
    
    const diff = Math.max(...diffArray);
    const sum = array.reduce((acc,cur)=>acc+cur,0)
    return (sum-diff) % (1e9+7)
};

오히려 더 간단하게 계산하기 위해, 차이가 큰 값에 대해서 계산해야한다고 강박이 생겨, 더 돌아가는 경우와 다른 경우를 하나하나 추가해야하나... 를 생각하느라 문제를 한번에 풀지 못했다.

그 외