[Leetcode]981. Time Based Key-Value Store

1. problem :

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

 

2. solution 1 :

from collections import defaultdict

class TimeMap:

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

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.timeDs or not self.timeDs[key]:
            return ''
        
        values = self.timeDs[key]
        left, right = 0, len(values) - 1

        # 이진 탐색
        while left <= right:
            mid = (left + right) // 2
            if values[mid][0] == timestamp:
                return values[mid][1]
            elif values[mid][0] < timestamp:
                left = mid + 1
            else:
                right = mid - 1
        
        # 정확한 값을 찾지 못했을 경우 가장 가까운 이전 값 반환
        if right >= 0:
            return values[right][1]
        return ''