[Leetcode][981] Time Based Key-Value Store

문제 : https://leetcode.com/problems/time-based-key-value-store/

---

timestamp를 key, value를 value로 하는 map을 하나만들고 이를 value 값으로 가지고 key값을 key로 가지는 unordered_map(정렬될 필요 없으므로)을 만든다.

unordered_map<string, map<int, string>> m; // {key, {timestamp, value}}

즉, 위와 같은 맵을 하나 만든다.

set할 때에는 key, timestamp, value를 자료형 타입과 맞게 m에 넣어준다.

get 할 때는 먼저 key값과 맞는 {timestamp, value}를 찾는다.

만약 하나도 없다면 빈 스트링을 반환한다.

맞는 map이 있다면 해당 맵에서 upper_bound를 이용해 timestamp 보다 하나 큰 요소를 찾는다.

왜 하나 큰 요소를 찾냐면 timestamp 보다 같거나 작은 value가 없는 경우 예외처리를 하기 쉽게 하기 위해서다.

timestamp보다 작거나 같은 value가 없는 경우 upper_bound(timestamp) 값은 맵의 가장 앞에 값이다. (m[key].begin())

만약 timestamp보다 작거나 같은 value가 있는 경우 결과는 맵의 가장 앞에 값이 나올 수 없다. 왜냐하면 upper_bound 값이기 때문에 맵의 가장 앞의 요소가 정답이라도 이 다음것이 결과로 나온다.

즉, upper_bound 값이 맵의 가장 앞의 요소라면 정답이 될 수 있는 value가 없는 경우이므로 빈 문자열을 반환한다.

이 외의 경우 찾은 요소의 이전 value를 반환한다.

---

소스코드 : https://gist.github.com/fpdjsns/359ef8a3b83792c2738295eb70fe6170