[Python] LeetCode - 981. Time Based Key-Value Store

LeetCode 981번 Time Based Key-Value Store 문제는 정해진 규칙대로 key-value store를 구현하는 문제다. 난이도는 중(Medium)이며 그리디 알고리즘을 통해 해결할 수 있다.

 

리트코드 981번 Time Based Key-Value Store 문제 정보

알고리즘 분류

- Greedy

난이도

- Medium

 

문제 요약

• Time-based key-value store를 구성하라.
• key는 원래 중복될 수 없지만, 다른 시간에 동일한 key가 존재할 수 있다.
• 시간은 무조건 증가하는 순서로 주어진다.
• set(key, value, timestamp)
  • 특정 key의 특정 timestamp의 value를 저장한다.
• get(key, timestamp)
  • 특정 key의 특정 timestamp의 value를 출력한다.
  • 만약 특정 timestamp에 저장된 값이 없으면, timestamp이전 가장 가까운 시간에 저장된 value를 출력한다.
  • 아예 없으면 “”를 출력한다.

 

문제 풀이 과정

 

• get을 위해 각 key마다 시간 순서대로 값이 저장되어야 한다. 그래서 각 key에 (시간, 값) 리스트를 생성하여 차곡차곡 저장했다. 시간은 무조건 순서대로 입력되므로 정렬은 필요 없다.

코드

class TimeMap:

    def __init__(self):
        self.map = collections.defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        for i in range(len(self.map[key])-1, -1, -1):
            t, v = self.map[key][i]
            if t <= timestamp:
                return v
        return ""
                
                


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

• 시간복잡도: set(): O(1), get(): O(N)
• 공간복잡도: O(N*M) (N: 시간, M: key 개수)