이번 글에서는 타임스탬프와 함께 데이터를 저장하고 조회할 수 있는 시간 기반 키-값 저장소(TimeMap) 클래스를 C++로 구현해 보겠습니다. 이 자료구조는 두 가지 연산을 지원해야 합니다.
- set(string key, string value, int timestamp): 주어진 키(key)에 값(value)과 타임스탬프(timestamp)를 함께 저장합니다.
- get(string key, int timestamp): 이전에 호출된 set(key, value, timestamp_prev) 중에서 timestamp_prev <= timestamp 조건을 만족하는 값을 반환합니다.
동작 규칙
조건을 만족하는 값이 여러 개 존재한다면, 그중 가장 큰 timestamp_prev를 가진 값을 반환해야 합니다. 만약 조건에 맞는 값이 하나도 없다면 빈 문자열("")을 반환합니다.
예를 들어 다음과 같이 함수를 호출한다고 가정해 보겠습니다.
set("foo", "bar", 1)
get("foo", 1)
get("foo", 3)
set("foo", "bar2", 4)
get("foo", 4)
get("foo", 5)이때 출력 결과는 순서대로 [null, "bar", "bar", null, "bar2", "bar2"]가 됩니다. get("foo", 3)의 경우 타임스탬프 1에 저장된 "bar"가 조건을 만족하므로 "bar"를 반환하고, get("foo", 5)는 타임스탬프 4에 저장된 "bar2" 중 가장 최신 값을 반환합니다.
해결 접근 방법
이 문제는 해시 맵과 이진 탐색(Binary Search)을 결합하면 효율적으로 해결할 수 있습니다. 알고리즘 단계는 다음과 같습니다.
- 키를 저장할 맵(map) m을 정의합니다. 각 키에는 (타임스탬프, 값) 쌍의 벡터가 매핑됩니다.
- set() 메서드: m[key]에 (timestamp, value) 쌍을 삽입합니다. 타임스탬프가 오름차순으로 입력된다는 전제 덕분에 별도의 정렬 없이 push_back만으로 해결됩니다.
- get() 메서드:
- 반환값 ret을 빈 문자열로 초기화합니다.
- v := m[key]로 해당 키의 (타임스탬프, 값) 목록을 가져옵니다.
- low := 0, high := v.size() - 1로 설정한 뒤 이진 탐색을 수행합니다.
- v[mid]의 타임스탬프가 주어진 timestamp보다 작거나 같으면, 해당 값을 ret에 저장하고 low := mid + 1로 갱신하여 더 최신 값을 찾습니다.
- 그렇지 않으면 high := mid - 1로 갱신하여 탐색 범위를 왼쪽으로 좁힙니다.
- 탐색이 끝나면 ret을 반환합니다.
이 방식은 set 연산이 O(1), get 연산이 O(log n)의 시간 복잡도를 가지므로 대량의 데이터에서도 빠른 성능을 보장합니다.
C++ 구현 코드
아래는 위 알고리즘을 실제로 구현한 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
class TimeMap {
public:
/** Initialize your data structure here. */
unordered_map <string, vector < pair <int, string> > > m;
TimeMap() {
m.clear();
}
void set(string key, string value, int timestamp) {
m[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
string ret = "";
vector <pair <int, string> >& v = m[key];
int low = 0;
int high = v.size() - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(v[mid].first <= timestamp){
ret = v[mid].second;
low = mid + 1;
}else{
high = mid - 1;
}
}
return ret;
}
};
main(){
TimeMap ob;
(ob.set("foo","bar",1));
cout << (ob.get("foo", 1)) << endl;
cout << (ob.get("foo", 3)) << endl;
(ob.set("foo","bar2",4));
cout << (ob.get("foo", 4)) << endl;
cout << (ob.get("foo", 5)) << endl;
}
입력 예시
객체를 생성한 후 set과 get 메서드를 아래 순서대로 호출합니다:
set("foo","bar",1))
get("foo", 1))
get("foo", 3))
set("foo","bar2",4))
get("foo", 4))
get("foo", 5))
출력 결과
bar
bar
bar2
bar2
마무리
시간 기반 키-값 저장소는 버전 관리 시스템, 캐시 만료 처리, 로그 조회 등 다양한 실무 상황에서 활용되는 개념입니다. 핵심은 타임스탬프의 정렬 특성을 활용한 이진 탐색입니다. unordered_map으로 O(1) 키 접근을 확보하고, 각 키의 값 목록에서 이진 탐색으로 원하는 시점의 값을 O(log n)에 찾아내는 이 조합은 면접에서도 자주 등장하는 클래식한 디자인 문제 패턴이니 꼭 익혀두시기 바랍니다.