[LeetCode] 985. Sum of Even Numbers After Queries

문제 출처: https://leetcode.com/problems/sum-of-even-numbers-after-queries/

Sum of Even Numbers After Queries - LeetCode

문제

정수로 이루어진 배열 nums와 쿼리 배열 queries가 주어진다.

 

i-번째 쿼리는 val = queries[i][0], index = queries[i][1]로, nums[index]에 val을 더하라는 의미이다. i-번째 쿼리에 대한 답은 nums 배열에서 짝수인 값의 합이다.

 

(index = queries[i][1]은 0부터 시작하며, 각 쿼리는 nums 배열을 수정한다.)

 

모든 쿼리에 대한 답을 반환하라. answer 배열은 i-번째 쿼리에 대한 답이 answer[i]에 있어야한다.

예제

Input: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]

Explanation: 
At the beginning, the array is [1,2,3,4].
After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

풀이

쿼리에 대한 답을 계산하기 위해서 어떠한 전략을 세우는지에 따라 성능이 좌우되는 문제이다.

 

첫 번째 방법으로는 하나의 쿼리가 끝날 때마다 배열을 순회하면서 짝수인 값들의 합을 계산하는 것이다.

function sumEvenAfterQueries(nums, queries) {
    const answer = [];

    for (let [val, index] of quries) {
        nums[index] += val;

        let evenSum = 0;
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) { evenSum += nums[i]; }
        }

        answer.push(evenSum);
    }

    return answer;
}

이 방식의 시간 복잡도는 쿼리의 수가 Q개, 배열(nums)의 크기가 N이라 할 때, O(Q x N)이 된다.

 

이 방법을 개선할 수 있는 방안에 대해 생각해보자.

 

위 방식에서 매 쿼리 수행마다 nums배열을 순회해야 하는가? 에 대해 의문이 든다. 쿼리로 인해 변경되는 값은 nums배열 중 하나의 값이다. 반대로 말하면, 하나를 제외하고 나머지 N-1개의 원소는 변하지 않는다는 것이다.

 

이 점을 토대로 최초 nums에서 짝수인 값의 합을 evenSum이라 할 때, 이 값과 쿼리로 인해 변경되는 값 사이의 관계를 찾아보면 아래와 같다.

evenSum = K 이고, query[x] = [val, index] 라고 하자.

쿼리 적용 전후의 nums[index]를 구분하기 위해 아래와 같이 이름을 붙여 생각해보자.
- beforeVal: 쿼리 적용 전의 nums[index]
- afterVal: 쿼리 적용 후의 nums[index]

- beforeVal 가 짝수일때, K 는 beforeVal 가 포함된 값
    - afterVal 가 짝수라면 K 에 val 만 더해주면 됨
    - afterVal 가 홀수라면, K 에서 beforeVal 를 빼줘야 함

- beforeVal 가 홀수일대, K는 beforeVal 가 미포함된 값
    - afterVal 가 짝수라면, K 에 새로운 짝수인 afterVal 를 더해줘야 함
    - afterVal 가 홀수라면, K 에 어떠한 영향도 없음

이러한 관계를 적용하여 코드를 작성하면 다음과 같다.

function sumEvenAfterQueries(nums, queries) {
    const answer = [];

    let evenSum = 0;
    for (let num of nums) {
        if (num % 2 == 0) { evenSum += num; }
    }

    for (let [val, index] of queries) {
        const before = nums[index] % 2 == 0 ? true : false;

        nums[index] += val;
        const after = nums[index] % 2 == 0 ? true : false;

        if (befroe && after) { evenSum += val; }
        else if (before && !after) { evenSum -= (nums[index] - val); }
        else if (!before && after) { evenSum += nums[index]; }

        ansewr.push(evenSum);
    }

    return answer;
}

코드는 조금 길어졌지만, 2중 반복문 구조에서 벗어나면서 시간 복잡도는 O(min(Q, N))으로 개선된 것을 알 수 있다.

 

Github: 985.js

opwe37/Algorithm-Study