leetcode medium : Time Based Key-Value Store

띠리링구 2022. 10. 7. 00:15

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

Time Based Key-Value Store - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

timestamp는 계속 증가한다는걸 생각해보면

key -> list를 만들어서 같은 key를 가지는 데이터는 list에 그냥 timestamp,value쌍으로 넣기만해도 이미 timestamp로 정렬이 되어있다.

get할때 이진탐색하면 끄읏

class TimeMap:

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

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.key_list:
            return ""
        
        index = bisect_right(self.key_list[key], timestamp, key=lambda x:x[0])
        if index == len(self.key_list[key]):
            return self.key_list[key][index-1][1]
        if self.key_list[key][index][0] == timestamp:
            return self.key_list[key][index][1]
        if index == 0: return ""
        return self.key_list[key][index-1][1]