[LeetCode 해석 및 풀이] 981. Time Based Key-Value Store

LeetCode 문제 해석 및 풀이 방법

 

문제 981. Time Based Key-Value Store(시간 기반 키-값 저장)

바로가기

 

문제 설명

영문

Design a time-based keyvalue 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 <= timestemp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

 

한글

같은 키에 여러 값을 다른 시간에 따라 저장할 수 있고, 특정 시간의 키의 값을 검색할 수 있는 시간 기반 키값 자료 구조를 디자인하십시오. 

 

TimeMap 클래스 구현:

• TimeMap() 자료 구조 초기화
• void set(String key, String value, int timestamp) 키 key와 값 value를 주어진 시간 timestamp에 저장
• String get(String key, int timestamp) timestamp_prev <= timestemp를 만족하는 set()이 이전에 호출될 때의 value값을 반환. 해당하는 값이 많다면, 가장 큰 timestamp_prev 값과 관련된 value 값을 반환. 만약 value가 없다면 ""를 반환.

 

제한조건

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 10^7
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 10^5 calls will be made to set and get.

 

입출력 예

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

 

해답 및 해설

 각 key마다 (value, timestamp)쌍으로 이루어진 배열을 만들어 둔다. 그 후 값을 넣을 때 이진 정렬로 값을 추가해 정렬 상태를 유지하고, 값을 찾을 때도 이진 정렬로 값을 찾는다. 이러면 출력은 시간복잡도가 O(log n)이 되나, 입력은 파이썬 기본 리스트의 한계 때문에 O(n)이 된다. (하지만 이번 문제에서는 set의 timestamps가 순증가한다 했으므로 입력시 상황은 신경쓰지 않아도 될 듯 싶다.)

입력 시에 시간복잡도도 O(log n)으로 만드는 방법으로는 이진 탐색 트리나 균형 이진 탐색 트리(AVL, 레드-블랙 트리) 등의 방법이 있지만 우선은 이진 탐색을 이용하기로 한다.

 

파이썬 (Python)

class TimeMap:
    def __init__(self):
        self.dict = defaultdict(list)

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

    def get(self, key: str, timestamp: int) -> str:
        value_list = self.dict.get(key)

        if not value_list or timestamp < value_list[0][1]: return ""
        if timestamp >= value_list[-1][1]: return value_list[-1][0]

        left = 0
        right = len(value_list)-1

        while left <= right:
            mid = (left + right) // 2
            if value_list[mid][1] < timestamp:
                left = mid + 1
            elif value_list[mid][1] > timestamp:
                right = mid - 1
            else:
                return value_list[mid][0]

        if value_list[mid][1] > timestamp:
            return value_list[mid-1][0]
        else:
            return value_list[mid][0]

시간이 처음보다 적거나 많을 때 빠르게 빠져나오고, 그렇지 않을 경우에는 이진 탐색으로 답을 구하는 해법. 마지막에 현재 timestamp보다 작은 값을 찾기 위한 처리도 해주었다.

 

while left + 1 < right:
    mid = (left + right) // 2
    if timestamp < timestamps[mid]:
        right = mid - 1
    else:
        left = mid + 1
    return vals[left]

마지막에 이렇게 처리하는 풀이도 있던데 왜 되는지는 잘 모르겠다.