[DSA][Binary Search] 06. Time Based Key-Value Store

LeetCode 981

 

06. Time Based Key-Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.
Implement the TimeMap class:
- TimeMap() Initializes the object of the data structure.
- void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
- String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp.
  If there are multiple such values, it returns the value associated with the largest timestamp_prev.
  If there are no values, it returns "".

 

 

[질문하기]

- 타임스탬프는 항상 증가하는 순서대로 호출되나요? YES

- 타임스탬프에 중복된 값이 들어올 수 있나요?

 

 

[아이디어]

- 키(key) 기준으로 각 타임스탬프와 값을 저장한다. get 시에는 해당 키의 타임스탬프 리스트에서 target timestamp 이하 중 가장 가까운 값을 이진탐색을 통해 찾는다. 

 

 

[풀이 1] Binary Search

class TimeMap:
    def __init__(self):
        self.hmap = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.hmap[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.hmap:
            return ""
        
        arr = self.hmap[key]
        idx = self.lowerbound(arr, timestamp)
        return arr[idx][1] if idx != -1 else ""
    
    def lowerbound(self, arr, target):
        l, r = 0, len(arr) - 1
        res = -1

        while l <= r:
            m = l + (r - l) // 2
            if arr[m][0] <= target:
                res = m
                l = m + 1
            else:
                r = m - 1

        return res

특정 timestamp에서 key에 해당하는 값을 가져와야 하는데, 정확한 timestamp가 존재하지 않는 경우에는 그보다 작거나 같은 가장 가까운 timestamp를 찾아야 한다. 이를 위해 우선 key를 기준으로, 각 timestamp와 그에 대응하는 value를 저장한다. set 연산은 timestamp가 오름차순으로 주어지기 때문에 각 key에 대해 (timestamp, value) 쌍을 리스트에 순차적으로 저장할 수 있다. 그 후 get 시에는 해당 key에 저장된 timestamp 목록에서 target timestamp 이하 중 가장 큰 값을 찾아야 한다. 이 과정을 O(n) 보다 빠르게 하기 위해 이진 탐색을 사용한다.

 

 

⏱️ 시간복잡도

 

• set은 단순히 해시맵에 값을 추가하는 연산이므로 O(1)의 시간 복잡도를 가진다.
• get은 저장된 타임스탬프 리스트에서 이진 탐색을 통해 값을 찾기 때문에 O(log n)의 시간 복잡도를 가진다.

 

🧠 공간복잡도

set이 호출될 때마다 key별로 (timestamp, value) 쌍을 저장하므로, m개의 서로 다른 키가 있고, 각 키당 최대 n개의 타임스탬프가 저장된다면 전체 공간 복잡도는 O(m × n)이다.