스냅샷 배열(Snapshot Array)이란?
스냅샷 배열은 배열의 상태를 여러 시점별로 기록하고, 나중에 특정 시점(스냅샷)의 값을 다시 조회할 수 있는 자료구조입니다. 이 문제에서는 다음 네 가지 인터페이스를 구현해야 합니다.
- SnapshotArray(int length) — 주어진 길이만큼 배열 형태의 자료구조를 초기화합니다. 초기에는 모든 요소가 0입니다.
- set(index, val) — 주어진 인덱스의 요소를 val 값으로 설정합니다.
- snap() — 현재 배열 상태의 스냅샷을 찍고, snap_id(지금까지 snap()이 호출된 횟수에서 1을 뺀 값)를 반환합니다.
- get(index, snap_id) — 주어진 snap_id의 스냅샷을 찍었던 시점 기준으로 해당 인덱스의 값을 반환합니다.
동작 예시
배열 크기가 2라고 가정해 보겠습니다. 먼저 set(0, 5)로 인덱스 0의 값을 5로 설정한 뒤 snap()을 호출하면 0이 반환됩니다. 이후 set(0, 6)으로 값을 변경하고 get(0, 0)을 호출하면, 스냅샷 0 시점의 값인 5가 반환됩니다.
문제 해결 접근 방법
핵심 아이디어는 스냅()을 호출할 때마다 전체 배열을 통째로 복사하는 대신, 각 인덱스별로 (스냅샷 ID, 값) 형태의 변경 이력만 저장하는 것입니다. 이 방식을 사용하면 메모리를 크게 절약할 수 있습니다.
1. 초기화 (__init__)
- current := 0 (현재 스냅샷 ID)
- arr := 길이 + 1개의 2차원 배열 [[0, 0]]으로 초기화
2. set(index, val)
- temp := arr[index]의 마지막 요소
- 만약 temp[0] == current라면, 같은 스냅샷 내에서의 수정이므로 arr[index] 마지막 요소의 두 번째 값만 val로 갱신합니다.
- 그렇지 않다면 [current, val]을 arr[index]에 새로 추가합니다.
3. snap()
- current를 1 증가시킨 뒤, current - 1을 반환합니다.
4. get(index, snap_id)
- temp := arr[index], low := 0, high := len(temp) - 1로 설정합니다.
- low < high 동안 반복합니다:
- mid := low + (high - low + 1) // 2
- temp[mid][0] <= snap_id이면 low := mid, 그렇지 않으면 high := mid - 1
- 반복이 끝나면 temp[low][1]을 반환합니다.
각 인덱스의 변경 이력은 스냅샷 ID 기준으로 오름차순 정렬되어 있으므로, 이진 탐색을 활용하면 주어진 snap_id 이하의 가장 최근 기록을 빠르게 찾을 수 있습니다.
파이썬 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
class SnapshotArray(object):
def __init__(self, length):
self.current = 0
self.arr = [[[0,0]] for i in range(length+1)]
def set(self, index, val):
temp = self.arr[index][-1]
if temp[0] == self.current:
self.arr[index][-1][1] = val
else:
self.arr[index].append([self.current, val])
def snap(self):
self.current += 1
return self.current - 1
def get(self, index, snap_id):
temp = self.arr[index]
low = 0
high = len(temp) - 1
while low < high:
mid = low + (high - low + 1)//2
if temp[mid][0] <= snap_id:
low = mid
else:
high = mid - 1
return temp[low][1]
ob = SnapshotArray(3)
ob.set(0, 5)
print(ob.snap())
ob.set(0, 6)
print(ob.get(0, 0))실행 결과
배열을 크기 3으로 초기화한 뒤, set(0, 5), snap(), set(0, 6), get(0, 0) 순서로 호출합니다.
출력:
0 5
시간 복잡도 분석
- set(): O(1)
- snap(): O(1)
- get(): O(log n) — n은 해당 인덱스의 변경 이력 개수
스냅샷을 찍을 때마다 전체 배열을 복사하는 단순한 방식(O(length) 소요)과 달리, 이 방식은 실제로 변경된 부분만 기록하므로 시간과 메모리 측면에서 모두 훨씬 효율적입니다.