정수로 이루어진 배열 A와 쿼리 배열 queries가 주어졌다고 가정해 봅시다. i번째 쿼리에서는 value = queries[i][0], index = queries[i][1]이며, 각 쿼리마다 A[index]에 value를 더하게 됩니다. 그런 다음 i번째 쿼리의 답은 배열 A에 남아 있는 짝수 값들의 합입니다. 우리가 해야 할 일은 모든 쿼리에 대한 답을 순서대로 담은 배열, 즉 answer[i]가 i번째 쿼리의 답이 되는 배열을 반환하는 것입니다.
문제 이해하기
예를 들어 배열이 [1, 2, 3, 4]이고, 쿼리 배열이 [[1,0], [-3,1], [-4,0], [2,3]]이라면 최종 답 배열은 [8, 6, 2, 4]가 됩니다.
- 초기 상태: [1, 2, 3, 4]
- 첫 번째 쿼리 (1, 0): A[0]에 1을 더하면 → [2, 2, 3, 4], 짝수의 합 = 2 + 2 + 4 = 8
- 두 번째 쿼리 (-3, 1): A[1]에 -3을 더하면 → [2, -1, 3, 4], 짝수의 합 = 2 + 4 = 6
- 세 번째 쿼리 (-4, 0): A[0]에 -4를 더하면 → [-2, -1, 3, 4], 짝수의 합 = -2 + 4 = 2
- 네 번째 쿼리 (2, 3): A[3]에 2를 더하면 → [-2, -1, 3, 6], 짝수의 합 = -2 + 6 = 4
이런 식으로 답 배열 [8, 6, 2, 4]를 얻게 됩니다.
접근 방법
매 쿼리마다 배열 전체를 다시 순회하며 짝수의 합을 구하면 비효율적입니다. 대신 현재 짝수의 합을 미리 계산해 두고, 변경된 인덱스만 부분적으로 갱신하는 방식을 사용하면 효율적으로 해결할 수 있습니다.
알고리즘 단계
- 결과를 저장할 배열
res를 정의합니다. sum := 0으로 초기화한 뒤, 배열 A의 각 요소 i를 확인하여 짝수라면 sum에 더합니다.- queries의 각 쿼리 i에 대해 다음을 수행합니다.
index := i[1],val := i[0]- 기존
A[index]가 짝수였다면 sum에서 해당 값을 빼줍니다. A[index] := A[index] + val로 값을 갱신합니다.- 갱신된
A[index]가 짝수라면 sum에 다시 더해줍니다. - 현재 sum을 res에 추가합니다.
- 모든 쿼리를 처리한 후 res를 반환합니다.
Python 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def sumEvenAfterQueries(self, A, queries):
result = []
sum = 0
for i in A:
if i % 2 == 0:
sum += i
for i in queries:
index = i[1]
val = i[0]
if A[index] % 2 == 0:
sum -= A[index]
A[index] += val
if A[index] % 2 == 0:
sum += A[index]
result.append(sum)
return result
ob1 = Solution()
print(ob1.sumEvenAfterQueries([1,2,3,4], [[1,0],[-3,1],[-4,0],[2,3]]))입력
[1,2,3,4] [[1,0],[-3,1],[-4,0],[2,3]]
출력
[8,6,2,4]
복잡도 분석
배열 A의 길이를 n, 쿼리의 개수를 q라고 할 때, 초기 짝수의 합 계산에 O(n), 각 쿼리 처리에는 O(1)이 걸리므로 전체 시간 복잡도는 O(n + q)입니다. 공간 복잡도는 답을 저장하는 배열을 제외하면 O(1)의 추가 공간만 사용합니다.