← 전체 회차
A-033● Day 332026.06.08mediumleetcode #981neetcode150

시간 기반 키-값 저장소

#hash-table#string#binary-search#design
↗ leetcode #981 · time-based-key-value-store
01

문제

· problem
P.033

시간 기반 키-값 저장소

↗ leetcode #981

같은 키에 대해 서로 다른 시간에 여러 값을 저장하고, 특정 시간에 해당하는 키의 값을 검색할 수 있는 시간 기반 키-값 데이터 구조를 설계하세요. TimeMap 클래스를 구현하세요: - TimeMap() 데이터 구조의 객체를 초기화합니다. - void set(String key, String value, int timestamp) 주어진 시간 timestamp에서 key 키와 value 값을 저장합니다. - String get(String key, int timestamp) 이전에 set이 호출되었으며, timestamp_prev <= timestamp를 만족하는 값을 반환합니다. 이러한 값이 여러 개 있다면, 가장 큰 timestamp_prev와 관련된 값을 반환합니다. 값이 없으면 빈 문자열 ""을 반환합니다.

제약
  • · 1 ≤ key.length, value.length ≤ 100
  • · All timestamps in set() are strictly increasing
  • · 1 ≤ timestamp ≤ 10^7
  • · At most 2 × 10^5 calls to set() and get()
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["TimeMap","set","get","get","set","get","get"]
[[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
[null, null, "bar", "bar", null, "bar2", "bar2"]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    주어진 키에 대해 set() 호출이 없을 때 get()은 무엇을 반환해야 합니까?
  • ☐
    두 개의 set() 호출 사이의 타임스탐프로 get()을 호출하면 어느 값을 반환해야 합니까?
  • ☐
    타임스탐프가 각 키에 대해 엄격히 증가하도록 보장됩니까?
  • ☐
    같은 키가 서로 다른 타임스탐프에서 여러 값을 가질 수 있습니까?
  • ☐
    값들을 저장한 후 타임스탐프를 정렬해야 합니까?
  • ☐
    정확히 같은 타임스탐프를 가진 여러 값의 경우를 처리해야 합니까?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 데이터 구조 초기화
○
self.keyStore = {}  # key : list of [val, timestamp]
○
self.keyStore = []
○
self.keyStore = set()
step 2· 키 존재 여부 확인 및 초기화│ 중첩
○
if key not in self.keyStore:
○
if key in self.keyStore:
○
if self.keyStore.get(key):
step 3· 값-타임스탐프 쌍 추가│ 중첩
○
self.keyStore[key].append([value, timestamp])
○
self.keyStore[key] = [value, timestamp]
○
self.keyStore[key].append(value)
step 4· 검색 초기화 및 값 리스트 조회
○
res, values = "", self.keyStore.get(key, [])
○
res, values = None, self.keyStore.get(key, [])
○
values = self.keyStore[key]
step 5· 이진 탐색 경계 설정
○
l, r = 0, len(values) - 1
○
l, r = 0, len(values)
○
l, r = 1, len(values) - 1
step 6· 이진 탐색: 조건 맞는 최대 타임스탐프 찾기│ 중첩
○
if values[m][1] <= timestamp:
○
if values[m][1] < timestamp:
○
if values[m][0] <= timestamp:
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class TimeMap:
2
    def __init__(self):
3
        """
4
        Initialize your data structure here.
5
        """
6
        self.keyStore = {}  # key : list of [val, timestamp]
7
8
    def set(self, key: str, value: str, timestamp: int) -> None:
9
        if key not in self.keyStore:
10
            self.keyStore[key] = []
11
        self.keyStore[key].append([value, timestamp])
12
13
    def get(self, key: str, timestamp: int) -> str:
14
        res, values = "", self.keyStore.get(key, [])
15
        l, r = 0, len(values) - 1
16
        while l <= r:
17
            m = (l + r) // 2
18
            if values[m][1] <= timestamp:
19
                res = values[m][0]
20
                l = m + 1
21
            else:
22
                r = m - 1
23
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["TimeMap","set","get","get","set","get","get"]
[[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
→
[null, null, "bar", "bar", null, "bar2", "bar2"]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.