LeetCode 981, Time Based Key-Value Store 파이썬, 풀이, 해설
접근
- dictionary 에 키에 해당하는 리스트를 만들고 오름차순의 input 을 받는다.
- get 부를때 해당 키의 리스트에서 binary search 로 최댓값을 찾는다.
사고
평범한 binary search 문제이다. 문제 조건에서 들어오는 timestamp 는 오름차순으로 찍힌다고 하는게 큰 길잡이이다.
from collections import defaultdict
class TimeMap:
dic = None
def __init__(self):
self.dic = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.dic[key].append([timestamp, value])
def get(self, key: str, timestamp: int) -> str:
lo, hi = 0, len(self.dic) - 1
ans = ""
while lo <= hi:
mid = (lo + hi) // 2
if self.dic[key][mid][0] > timestamp:
hi = mid - 1
else:
ans = self.dic[key][mid][1]
lo = mid + 1
return ans
