LeetCode

LeetCode 981 Time Based Key-Value Store 풀이: 키별 시간 배열과 이분 탐색

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

키마다 시간순으로 기록을 관리하고, 조회 시각보다 늦지 않은 기록 중 가장 최근 값을 찾아야 한다. 해시 맵으로 키별 이력을 나누고 각 이력에서 경계 이분 탐색을 적용하므로 Level 3으로 판단했다.

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

시간에 따라 같은 키에 여러 값을 저장하고, 특정 시각에 유효한 값을 조회하는 TimeMap을 구현한다.

  • set(key, value, timestamp): 키와 값을 해당 timestamp에 저장한다.
  • get(key, timestamp): 해당 시각 이하에서 timestamp가 가장 큰 기록의 value를 반환한다.
  • 조건에 맞는 기록이 없으면 빈 문자열 ""을 반환한다.

중요한 조건은 다음과 같다.

  • set 호출의 timestamp는 전체 호출에서 엄격히 증가한다.
  • 동일 키에 저장되는 timestamp도 증가 순서로 들어옵니다.
  • 최대 2 * 10^5회의 호출이 주어집니다.
  • get은 정확히 같은 시각의 값이 없어도 과거의 가장 가까운 값을 반환해야 한다.

예를 들어 foo에 시각 1의 bar를 저장하고 get("foo", 3)을 호출하면, 시각 3의 기록은 없더라도 시각 1이 가장 최근의 이전 기록이므로 bar를 반환한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

키별 시간순 기록

해시 맵 store에서 각 키를 해당 키의 (timestamp, value) 목록에 연결한다.

store[key] = [(timestamp_1, value_1), (timestamp_2, value_2), ...]

timestamp가 증가하는 순서로 set이 호출되므로 각 키의 목록도 자동으로 정렬된 상태를 유지한다. 새 기록은 목록 끝에 추가하면 된다.

핵심 관찰: 조회는 floor 탐색

get(key, timestamp)의 요구사항은 저장 시각 중 조회 시각 이하인 값들의 최댓값을 찾는 것입니다.

가장 오른쪽 timestamp <= query timestamp

이는 정렬된 목록에서 특정 값 이하인 마지막 위치를 찾는 이분 탐색입니다. 조회 시각과 timestamp가 정확히 일치할 필요는 없으며, 조회 시각보다 뒤의 기록은 후보가 될 수 없다.

판정 함수와 탐색 구간

목록의 중간 기록을 확인하면서 다음 규칙으로 범위를 좁힌다.

  • history[mid].timestamp <= timestamp이면 해당 기록은 답 후보다. 더 최근의 유효 기록이 오른쪽에 있을 수 있으므로 left = mid + 1로 이동한다.
  • history[mid].timestamp > timestamp이면 미래의 기록이므로 right = mid - 1로 이동한다.

반복이 끝난 뒤 right는 timestamp 이하인 마지막 인덱스다. right < 0이면 조건을 만족하는 기록이 하나도 없으므로 ""을 반환한다.

이력의 timestamp가 [1, 4, 8]이고 조회 시각이 6이라고 하자. 중간값 4는 유효한 후보이므로 오른쪽을 더 살핀다. 다음 값 8은 조회 시각보다 늦어 왼쪽으로 물러난다. 탐색이 끝나면 right는 1이고, 시각 4에 저장한 값이 답으로 남는다.

해시 맵과 이분 탐색을 함께 쓰는 이유

해시 맵은 키에 해당하는 이력 목록을 평균 O(1)에 찾는다. 목록 내부에서는 시간순 정렬을 이용해 조회를 O(log k)에 처리한다. 여기서 k는 해당 키에 저장된 기록 수다.

모든 기록을 하나의 전역 목록에 넣으면 다른 키의 기록까지 검색 범위에 섞인다. 키별로 목록을 나누면 각 이력의 timestamp 정렬 상태를 직접 활용할 수 있다.

오답 접근과 반례

정확한 timestamp만 찾으면 조회 시각이 저장 시각 사이에 놓인 경우를 처리하지 못한다. 시각 6의 조회에는 시각 4의 값을 반환해야 한다. 전체 이력을 순회해도 답을 찾을 수 있지만, get 한 번에 O(k)가 걸린다. 정렬된 이력에서 마지막 유효 시각만 이분 탐색하는 편이 낫다.

키가 없는 경우뿐 아니라 첫 기록보다 이른 시각을 조회할 때도 빈 문자열을 반환해야 한다.

시간·공간 복잡도

set은 키별 목록 끝에 쌍을 추가하므로 평균 O(1)이다. get은 키별 기록 수를 k라고 할 때 O(log k)다. 전체 저장 공간은 모든 키에 추가한 기록 수를 N이라고 하면 O(N)이다.

3. 문제 해결 코드 (Python)

store는 키별 (timestamp, value) 목록을 보관한다. get에서는 닫힌 구간 이분 탐색으로 조회 시각 이하인 마지막 기록의 위치를 찾는다.

from collections import defaultdict


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

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

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

        left = 0
        right = len(history) - 1
        answer_index = -1

        while left <= right:
            mid = left + (right - left) // 2

            if history[mid][0] <= timestamp:
                answer_index = mid
                left = mid + 1
            else:
                right = mid - 1

        if answer_index == -1:
            return ""
        return history[answer_index][1]

조건을 만족하는 기록을 찾을 때마다 answer_index를 갱신하고 더 오른쪽을 탐색한다. 이렇게 하면 조회 시각 이하의 기록 중 가장 최근 값을 선택할 수 있다. 각 키의 timestamp가 증가하므로 set에서는 별도의 삽입 위치 탐색이나 정렬이 필요하지 않다.

복사해 실행할 테스트

아래 연산을 TimeMap 클래스 아래에 붙여 같은 Python 파일에서 실행하면 정확한 시각, 사이 시각, 키 누락, 첫 기록 이전 조회를 확인할 수 있다.

time_map = TimeMap()
time_map.set("foo", "bar", 1)
assert time_map.get("foo", 1) == "bar"
assert time_map.get("foo", 3) == "bar"
time_map.set("foo", "bar2", 4)
assert time_map.get("foo", 5) == "bar2"
assert time_map.get("missing", 10) == ""
assert time_map.get("foo", 0) == ""

4. 공식 예제와 추가 검증

작성한 TimeMap 클래스를 Python으로 실행해 공식 연산과 exact match, 사이 시각, 키 누락, 첫 timestamp 이전 조회를 확인했다.

공식 예제

연산:
set("foo", "bar", 1)
get("foo", 1) -> "bar"
get("foo", 3) -> "bar"
set("foo", "bar2", 4)
get("foo", 4) -> "bar2"
get("foo", 5) -> "bar2"

기대 출력: [null, "bar", "bar", null, "bar2", "bar2"]
확인 결과: 통과
검증 목적: 정확한 시각과 사이 시각에서 가장 최근의 과거 값을 반환하는지 확인

추가 검증 1: 첫 기록보다 이른 시각

연산:
set("key", "value", 5)
get("key", 4) -> ""
확인 결과: 통과
검증 목적: query 이하의 timestamp가 없을 때 빈 문자열을 반환하는지 확인

추가 검증 2: 존재하지 않는 키

연산:
get("missing", 10) -> ""
확인 결과: 통과
검증 목적: 키 이력이 없는 경우를 안전하게 처리하는지 확인

추가 검증 3: 여러 키의 독립된 기록

연산:
set("a", "A1", 1)
set("b", "B2", 2)
set("a", "A3", 3)
get("a", 2) -> "A1"
get("b", 3) -> "B2"
확인 결과: 통과
검증 목적: 키마다 이력 목록이 분리되어 조회되는지 확인

추가 검증 4: timestamp 사이에 여러 기록이 있는 경우

연산:
set("key", "v1", 2)
set("key", "v2", 5)
set("key", "v3", 9)
get("key", 7) -> "v2"
확인 결과: 통과
검증 목적: query 이전의 가장 큰 timestamp를 선택하는지 확인

5. 다른 풀이 방식 검색 및 비교

모든 timestamp를 순차 탐색하면 구현은 간단하지만 get 한 번에 O(k) 시간이 든다. 키별 기록이 이미 정렬되어 있으므로 이분 탐색을 이용하면 조회 시간을 O(log k)로 줄일 수 있다.

정렬 맵이 있는 언어에서는 floorEntry(timestamp) 같은 연산으로 같은 경계를 찾을 수 있다. Python에서는 리스트와 이분 탐색을 직접 사용해 동작을 명확하게 구현할 수 있다.

마무리

Time Based Key-Value Store는 각 키의 변경 이력을 시간순으로 저장하고 과거 시점의 값을 조회하는 자료구조 설계 문제다. timestamp가 증가하는 순서로 들어오므로 set은 목록 끝에 추가하고, get은 이분 탐색으로 조회 시각 이하의 가장 최근 기록을 찾으면 된다.

관련 문제

#이분탐색#LeetCode#난이도 3