숫자 리스트 nums와 연산 리스트가 주어졌을 때, 각 연산은 세 개의 필드 [L, R, X]로 구성됩니다. 이는 인덱스 L부터 R까지(양 끝 포함)의 모든 요소를 X만큼 증가시키라는 의미입니다. 모든 연산을 적용한 후 최종 리스트를 반환해야 합니다.
문제 예시
입력이 다음과 같다고 가정해 보겠습니다.
- nums = [8, 4, 2, -9, 4]
- operations = [[0, 0, 3], [1, 3, 2], [2, 3, 5]]
이 경우 출력은 [11, 6, 9, -2, 4]가 됩니다. 연산 과정을 단계별로 살펴보면 다음과 같습니다.
- 첫 번째 연산 [0, 0, 3] 수행 → 리스트는 [11, 4, 2, -9, 4]
- 두 번째 연산 [1, 3, 2] 수행 → 리스트는 [11, 6, 4, -7, 4]
- 세 번째 연산 [2, 3, 5] 수행 → 리스트는 [11, 6, 9, -2, 4]
해결 전략: 이벤트 기반 누적 기법
각 연산마다 리스트를 직접 순회하며 값을 더하는 방식은 비효율적일 수 있습니다. 대신 차분 배열(Difference Array) 개념을 활용한 이벤트 기반 접근법을 사용하면 효율적으로 해결할 수 있습니다.
해결 단계는 다음과 같습니다.
- 빈 리스트
events를 생성합니다. - operations의 각 (l, r, inc)에 대해:
- (l, inc)를 events의 끝에 추가합니다.
- (r + 1, -inc)를 events의 끝에 추가합니다.
- events 리스트를 정렬합니다.
- inc = 0, ptr = 0으로 초기화합니다.
- i를 0부터 nums의 크기까지 반복하면서:
- ptr이 events의 크기보다 작고 events[ptr][0]이 i와 같은 동안:
- inc에 events[ptr][1]을 더합니다.
- ptr을 1 증가시킵니다.
- nums[i]에 inc를 더합니다.
- ptr이 events의 크기보다 작고 events[ptr][0]이 i와 같은 동안:
- nums를 반환합니다.
핵심 아이디어는 각 구간의 시작점에서 증가값을 기록하고, 끝나는 지점 다음 인덱스에서 그 값을 상쇄하는 것입니다. 이렇게 하면 한 번의 순회로 모든 구간 업데이트를 처리할 수 있습니다.
구현 예제
class Solution:
def solve(self, nums, operations):
events = []
for l, r, inc in operations:
events.append((l, inc))
events.append((r + 1, -inc))
events.sort()
inc = 0
ptr = 0
for i in range(len(nums)):
while ptr < len(events) and events[ptr][0] == i:
inc += events[ptr][1]
ptr += 1
nums[i] += inc
return nums
ob = Solution()
nums = [8, 4, 2, -9, 4]
operations = [ [0, 0, 3], [1, 3, 2], [2, 3, 5] ]
print(ob.solve(nums, operations))입력
[8, 4, 2, -9, 4], [[0, 0, 3], [1, 3, 2], [2, 3, 5]]
출력
[11, 6, 9, -2, 4]
복잡도 분석
이 방법의 시간 복잡도는 O(N + M log M)입니다. 여기서 N은 리스트의 길이, M은 연산의 개수입니다. 정렬에 O(M log M), 최종 순회에 O(N + M)이 소요됩니다. 각 연산마다 구간 전체를 순회하는 단순한 방식(O(N × M))에 비해 훨씬 효율적이며, 특히 연산 범위가 넓고 연산 횟수가 많을 때 그 장점이 두드러집니다.