Leetcode 1146. Snapshot Array

https://leetcode.com/problems/snapshot-array/description/

Snapshot Array - LeetCode

 

문제

SnapshorArray를 아래와 같은 지시에 따라 구현하라

• SnapShotArray(int length) 주어진 길이만큼 초기화. 처음의 경우 각 엘레멘트는 0이 된다
• void set(index, val) 주어진 index에 val의 값을 설정한다
• int snap(), 스냅샷을 생성한다. 이때 생성된 snap_id를 반환한다. 이 snap_id는 snap 메소드를 호출한 횟수의 -1이 된다.
• int get(index, snap_id) 특정한 snap_id에 있었던 index의 값을 반환한다.

코드

from collections import defaultdict

class SnapshotArray:

    def __init__(self, length: int):

        self.array = defaultdict(dict)

        self.cur_id = 0

    def set(self, index: int, val: int) -> None:

        if self.array[self.cur_id] is self.array[self.cur_id-1]:

            self.array[self.cur_id] = self.array[self.cur_id -1].copy()

           

        self.array[self.cur_id][index] = val

    def snap(self) -> int:

        self.array[self.cur_id + 1] = self.array[self.cur_id]

        self.cur_id += 1

        self.need_save = False

        return self.cur_id - 1

    def get(self, index: int, snap_id: int) -> int:

        if index not in self.array[snap_id]:

            return 0

        return self.array[snap_id][index]

---

snap_id가 새로 생성될 때 마다 이전의 array를 복사하니 메모리 초과가 발생하여, 수정이 있을 때만 복사하고 그렇지 않은 경우 이전의 array에 대해 참조를 걸어두어 메모리를 최소화 함. 또한 SnapshotArray를 초기화 할 때 주어지는 길이 파라미터 만큼 초기화 할 경우 역시 메모리 초과가 발생하여 필요한 부분만 사용하도록 dictionary를 사용함.