LC 981. Time Based Key-Value Store

문제 개요

• 기본적으로 key, value 쌍이 저장되는 해쉬맵을 만드는 것이 목표입니다.

• 추가로 요구하는 점은 time stamp가 같이 저장되어서 같은 key에 여러 value가 들어간다는 점입니다.

• 같은 key와 value더라도 timestmap로 구분되게 됩니다.

• 또 하나의 요건은 get요청시 같은 key가 여러개라면 기존 timestmap의 가장 큰 것과 가까운 key, value 쌍을 반환하라고 하는 것입니다.

• 만약 (key, value) 형태로 ("foo", 1)이 있을 때 get("foo", 2) 하더라도 key "foo"인 값이 출려되는 거죠.
  정확히 인수로 넣어준 timestmap에 상응하는 값이 없더라도 이전 타임스탬프의 가장 큰 값으로 판단해서 반환하면 됩니다.

• 구현 문제라서 기본 코드 구조가 다릅니다.

class TimeMap:

    def __init__(self):

    def set(self, key: str, value: str, timestamp: int) -> None:

    def get(self, key: str, timestamp: int) -> str:


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

• 어떻게 풀지 구상해봅시다.

풀이 구상

• key, value 쌍이므로 TimeMap은 딕셔너리로 초기화 해줘야겠군요.

• set도 해쉬맵과 다를 건 없어 보입니다.

• get 요청에서 이진탐색을 적용할 수 있습니다. 이진탐색이 적용 가능하다고 판단한 이유는 제약사항에 All the timestamps timestamp of set are strictly increasing.
  즉, set 해서 해쉬맵에 등록 할 때 timestmap에 따라 오름차순 정렬되어 저장 되어야 하네요.

• 정렬 되어있으니 이진탐색 O(logn)이 가능합니다.
  만약 정렬되어 있지 않았으면 O(nlogn)으로 그냥 brute force(O(n))이 나을 뻔 했습니다.

• 고려해야할 사항은
  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 "".
  이 부분입니다.

• 같은 key를 가진 값이 여러개라면, 이전 타임스탬프의 값이 가장 큰 값으로 반환해야 한다는 뜻입니다.

• 정렬되어 있으므로 이진탐색으로 빠르게 찾을 수 있습니다.

• 이해가 잘 안된다면 이렇게 그림을 그려 보면 좀 더 쉽게 파악할 수 있습니다.
  

문제해결 코드

class TimeMap:

    def __init__(self):
        # 딕셔너리 생성
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # 딕셔너리에 key, value 쌍 추가
        if key not in self.store:
            self.store[key] = []
        self.store[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        values = self.store.get(key, [])
        res = ''
        l, r = 0, len(values) - 1
        
        while l <= r:
            m = (l + r) // 2
            # 입력 받은 timestmap와 같거나 작은 값 탐색: 이전 timestamp 중 가장 큰 값
            if values[m][1] <= timestamp:
                res = values[m][0]
                l = m + 1
            else: 
                r = m - 1
        return res

• 시간복잡도는 get: O(logn)입니다.