981. 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 "".

https://leetcode.com/problems/time-based-key-value-store/

접근

#자료구조 #이진탐색 #맵(딕셔너리)

자료구조에 대한 이해가 필요하다. init은 객체를 만들 때에 가장 먼저 선언되는 부분이므로, 이곳에 key와 [ timestamp, value ] 를 저장할 맵을 만든다.

set은 생성한 맵에 자료를 넣는 함수이다. 받아온 key를 확인한 후 key가 존재하지 않으면 생성한다. 이후 받아온 값을 리스트로 만들어 저장한다.

get은 맵에 저장된 자료를 불러오는 함수이다. 이때 매개변수로 주어진 timestamp값을 사용해(이하 t), 주어진 t값보다 작되 같은 조건의 값들보다는 가장 큰 timestamp값을 가진 자료를 꺼내어 리턴한다.
이 과정에서 브루트 포스 탐색을 하면 시간이 길어질 우려가 있으므로, 이진탐색 알고리즘을 사용해 탐색 시간을 줄였다.

코드

class TimeMap:

    def __init__(self): # 초기화
        self.kt_map = {} 

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.kt_map:
            self.kt_map[key] = [] # 키가 없을 시 생성함
            
        self.kt_map[key].append([timestamp,value]) # key에 따른 시간과 값 쌍을 저장함

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.kt_map or timestamp < self.kt_map[key][0][0]: # 요청한 키가 없을 시, 주어진 시간보다 적은 시간이 없을시 빈 문자열 리턴
            return "" 
        
        left = 0
        right = len(self.kt_map[key])
        
        # 이진탐색
        while left<right:
            mid = (left+right)//2
            if self.kt_map[key][mid][0] <= timestamp: # mid번째 쌍의 시간이 주어진 것보다 작으면
                left = mid+1
            else:
                right = mid
        return "" if right == 0 else self.kt_map[key][right-1][1]


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

효율성

Runtime: 2262 ms, faster than 6.66% of Python3 online submissions for Time Based Key-Value Store.
Memory Usage: 72.2 MB, less than 34.33% of Python3 online submissions for Time Based Key-Value Store.