[LeetCode 2918] Minimum Equal Sum of Two Arrays After Replacing Zeros

문제개요

문제: https://leetcode.com/problems/minimum-equal-sum-of-two-arrays-after-replacing-zeros

 

두 개의 양의 정수 배열 nums1, nums2가 주어집니다. 이 배열들에는 0이 포함되어 있을 수 있으며, 이 0들을 양의 정수(1 이상)로 대체해야 합니다. 목표는 두 배열의 모든 원소의 합이 같도록 만드는 것입니다. 두 배열의 합이 같은 경우 중 가장 작은 합을 반환하고, 그러한 경우가 없다면 -1을 반환해야 합니다.

 

예를 들어, 다음과 같은 두 개의 배열이 있다고 가정한다면,

nums1 = [3, 2, 0, 1, 0]

nums2 = [6, 5, 0]

 

0들을 아래와 같이 대체할 수 있습니다:

 

• nums1의 두 개의 0 → 2, 4로 교체 → [3, 2, 2, 1, 4] → 총합: 12
• nums2의 하나의 0 → 1로 교체 → [6, 5, 1] → 총합: 12

 

결과적으로 두 배열의 합이 동일해지며,

이 경우가 만들 수 있는 최소의 동일 합입니다.

 

접근방식

두 배열에 있는 모든 0을 양의 정수로 바꾸고, 두 배열의 합이 같도록 만드는 것이 이 문제의 목표입니다.

모든 0을 1로 바꾸면 해당 배열의 합을 최소값으로 만들 수 있다는 점은 쉽게 떠올릴 수 있습니다.

 

우선, sum1, sum2를 각각 nums1, nums2 배열의 0이 아닌 원소들의 합이라고 합시다.

또한, zero1, zero2를 두 배열에 포함된 0의 개수라고 하면, 각 배열이 가질 수 있는 최소 합은 다음과 같이 표현됩니다:

 

• nums1의 최소 합: sum1 + zero1
• nums2의 최소 합: sum2 + zero2

 

이제 다음과 같은 조건을 고려할 수 있습니다.

 

1. 양쪽 배열에 0이 하나 이상 있을 경우

항상 해결 방법이 존재합니다. 이 경우, 두 배열이 같아질 수 있는 최소 합은 다음과 같습니다

max(sum1 + zero1, sum2 + zero2)

 

2.한쪽 배열에만 0이 없고, 다른 한쪽의 최소 가능한 합이 이 고정된 합보다 클 경우

이 경우엔 어떤 수를 넣어도 두 배열의 합이 같아질 수 없습니다.

구현

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:

        sum1 = sum(nums1)
        sum2 = sum(nums2)
        zero1 = nums1.count(0)
        zero2 = nums2.count(0)

        sum1 += zero1
        sum2 += zero2

        if (sum1 < sum2 and zero1 == 0) or (sum1 > sum2 and zero2 == 0):
            return -1

        return max(sum1, sum2)

 

시간 복잡도의 경우는 nums1, nums2 두 배열의 길이를 각각 n, m이라고 한다면 시간복잡도는 O(n+m)입니다. 각 배열을 순회하면서 0의 개수를 세어주기 때문입니다.

 

공간 복잡도의 경우 단순히 변수로만 문제를 해결하였기 때문에, O(1) 즉, 상수 공간입니다.