BST: 981. Time Based Key-Value Store ★★★

981. Time Based Key-Value Store

 

class TimeMap:

    def __init__(self):
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []    
        self.store[key].append([timestamp, value])
        # self.store[key].sort(key=lambda x: -x[0])


    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""

        # 타임스탬프 배열 추출
        timestamps = [t[0] for t in self.store[key]]

        # 이진 탐색 직접 구현
        l, r = 0, len(timestamps) - 1
        while l <= r:
            mid = (l + r) // 2
            if timestamps[mid] <= timestamp:
                l = mid + 1  # 유효한 값을 찾았으니 더 오른쪽을 탐색
            else:
                r = mid - 1  # 유효하지 않은 값을 제외하고 왼쪽을 탐색

        # r이 유효한 타임스탬프의 인덱스를 가리킴
        if r >= 0:
            return self.store[key][r][1]  # 해당 값 반환
        return ""  # 유효한 타임스탬프가 없으면 빈 문자열 반환



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

 

시간 제한에 걸림!!

 

https://youtu.be/fu2cD_6E8Hw?si=2B5C7UUzdufVSx6H

 

class TimeMap:

    def __init__(self):
        # store는 key를 문자열로, value를 [값, 타임스탬프]의 리스트로 저장합니다.
        # `store` stores key-value pairs where the key is a string, 
        # and the value is a list of [value, timestamp].
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # 만약 key가 store에 없다면 초기화합니다.
        # If the key is not in the store, initialize it with an empty list.
        if key not in self.store:
            self.store[key] = []
        # key에 [value, timestamp]를 추가합니다.
        # Append the [value, timestamp] to the list corresponding to the key.
        self.store[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        # 반환값을 저장할 변수 res를 초기화합니다.
        # Initialize the result variable `res` to store the value to return.
        res = ""

        # store에서 key에 해당하는 값을 가져오며, 없으면 빈 리스트를 반환합니다.
        # Retrieve the list of values for the given key from the store, or return an empty list.
        values = self.store.get(key, [])

        # 이진 탐색을 위해 왼쪽(l)과 오른쪽(r) 포인터를 설정합니다.
        # Set up left (`l`) and right (`r`) pointers for binary search.
        l, r = 0, len(values) - 1

        # 이진 탐색 루프를 시작합니다.
        # Start the binary search loop.
        while l <= r:
            # 중간값 인덱스를 계산합니다.
            # Calculate the middle index.
            mid = (l + r) // 2
            # 중간값의 타임스탬프가 주어진 타임스탬프 이하인 경우
            # If the timestamp at `mid` is less than or equal to the given timestamp:
            if values[mid][1] <= timestamp:
                # 해당 값을 결과(res)로 저장합니다.
                # Save the corresponding value to the result (`res`).
                res = values[mid][0]
                # 더 큰 타임스탬프를 찾기 위해 왼쪽 포인터를 오른쪽으로 이동합니다.
                # Move the left pointer (`l`) to search for larger timestamps.
                l = mid + 1
            else:
                # 중간값의 타임스탬프가 주어진 타임스탬프보다 큰 경우
                # If the timestamp at `mid` is greater than the given timestamp:
                # 더 작은 타임스탬프를 찾기 위해 오른쪽 포인터를 왼쪽으로 이동합니다.
                # Move the right pointer (`r`) to search for smaller timestamps.
                r = mid - 1

        # 찾은 값(res)을 반환합니다. 값이 없으면 빈 문자열을 반환합니다.
        # Return the found value (`res`). If no value is found, return an empty string.
        return res


# Your TimeMap object will be instantiated and called as such:
# 아래는 클래스의 사용 예입니다.
# Example usage of the class:
# obj = TimeMap()
# 새로운 키와 값을 설정합니다.
# Set a new key-value pair with a timestamp.
# obj.set(key, value, timestamp)
# 특정 키와 타임스탬프에 대한 값을 가져옵니다.
# Retrieve the value for a given key and timestamp.
# param_2 = obj.get(key, timestamp)