[LeetCode] 981 | Time Based Key-Value Store | Python

---

문제 링크: https://leetcode.com/problems/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 "".

---

조건

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= $10^7$
• All the timestamps timestamp of set are strictly increasing.
• At most $2 * 10^5$ calls will be made to set and get.

---

내 풀이

key와 (value, timestamp)를 dictionary형태로 저장한다.

get 할 때는 binary search를 이용해 찾는 시간을 줄인다.

---

코드

class TimeMap:

    def __init__(self):
        self.dict = defaultdict(list)

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

    def get(self, key: str, timestamp: int) -> str:
        values = self.dict[key]
        left, right = 0, len(values)
        
        while left < right:
            mid = (left + right) // 2
            
            if values[mid][1] <= timestamp:
                left = mid + 1
            else:
                right = mid
        
        if left == 0:
            return ''
        return values[left-1][0]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)