1775. Equal Sum Arrays With Minimum Number of Operations [Medium]

https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/

Equal Sum Arrays With Minimum Number of Operations - LeetCode

 

1부터 6까지의 목록을 주고, 각 목록의 요소 값을 한 번에 1~6 중에서 임의로 변경시킬 수 있다고 할 때, 두 목록의 합을 같게 만드는데 몇번의 과정이 필요한지 구하는 문제이다.

 

해보려고하니 막상 떠오르지가 않는다.

처음에는 두 목록의 동일한 인자를 체크한 뒤 제외해가며 재귀를 돌려고 했는데 합을 구하는 문제기 때문에 이게 최선이 아니라고 생각했고.. 결국 두 목록을 돌면서 합을 비교하면서 요소를 수정해야된다고 생각이 들었다.

 

1일 1문제를 풀려고 켜긴했으나 백신 부작용인가.. 모르겠지만 X사와 속 메스꺼움으로 잠을 못자고 상태가 너무 좋지 않아서 그런가 뭔가 쉽지 않다..

 

결국 다른 사람의 풀이를 보았는데 대략적인건 비슷하지만 실제 구현은 역시 쉽지 않았던 것 같다.

그들의 코드와 설명을 보고 이해했는데... 보고나면 쉽다..

 

static constexpr int maximum = 6; // 대전제
int minOperations(vector<int>& nums1, vector<int>& nums2) {
    // 1 * (6)과 (1) * 7개는 암만해도 안되기 때문에
    if (nums1.size() * maximum < nums2.size() || nums2.size() * maximum < nums1.size()) {
        return -1;
    }

    int sum1 = std::accumulate(begin(nums1), end(nums1), 0);
    int sum2 = std::accumulate(begin(nums2), end(nums2), 0);

    // nums1에 합이 작은 목록이, nums2에 합이 큰 목록이 오도록
    if (sum1 > sum2) {
        swap(nums1, nums2);
    }

    int gain[maximum] = { 0, };
    int diffsum = abs(sum1 - sum2);
    int ret = 0;

    // 각자 현 상태에서 얼마나 변화를 줄 수 있는지 기록..
    for (int n : nums1) {
        ++gain[maximum - n];
    }
    for (int n : nums2) {
        ++gain[n - 1];
    }

    // 높은 값부터 내림차순으로 체크
    for (int i = maximum - 1; i > 0 && diffsum >= 0; --i) {
        // 앞에서 기록한 gain을 가지고 합의 차를 제거해나감
        int add = min(gain[i], diffsum / i + (0 != diffsum % i));
        diffsum -= add * i;
        ret += add;
    }

    return ret;
}