[LeetCode] 981. Time Based Key-Value Store with lower_bound

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

Time Based Key-Value Store - LeetCode

아..역시나 이번에도 시간 초과가 발생한다...

뇌절의 연속

내가 이렇게나 비효율적인 사람이었나 싶다.

그나마 효율적인 탐색을 하겠다고 Binary Search, (B+Tree로 구현된 STL인)Set 등 다양하게 시도하였으나 모두 FAIL

이보다 더 효율적인 방법이 도저히 떠오르지 않아서 Discussion에 찾아보니 모두 나와 같은 방법을 써서 탐색을 하더이다..

 

더 궁금해져서 열심히 시도해보니 lower_bound를 잘못 쓰는 바람에 비효율적인 구현을 해서 그랬다..

위의 메소드로 탐색 시에 통과되나, 아래 메소드는 통과되지 않았다.

auto value = timeMap[key].lower_bound({timestamp, ""});
auto value = lower_bound(timeMap[key].begin(), timeMap[key].end(), pair<int, string>(timestamp, ""));

알고보니 std::lower_bound와 set의 전용 메소드인 lower_bound의 구현 방식은 달랐다.

set의 lower_bound는 내가 앞서 말했던 균형 트리의 장점을 활용해 의도한대로 탐색을 할 수 있고, 시간복잡도도 O(log n) 맞출 수 있다.

하지만 std::lower_bound의 시간복잡도는 평소에는 $O(log n)$이나, 랜덤 액세스가 안되는 set, multiset에서는 $O(n)$으로, 원하는대로 효율적인 탐색이 되지 않는다.

 

 

참고) std::lower_bound vs. set.lower_bound

https://codeforces.com/blog/entry/64546

Difference Between std::lower_bound(set.begin(), set.end(), val) and set.lower_bound(val)? - Codeforces

https://www.geeksforgeeks.org/difference-between-stdsetlower_bound-and-stdlower_bound-in-c/

Difference between std::set::lower_bound and std::lower_bound in C++ - GeeksforGeeks

set을 사용한 풀이

class TimeMap {
public:
    unordered_map<string, set<pair<int, string>>> timeMap;
    TimeMap() {
        timeMap.clear();
    }
    
    void set(string key, string value, int timestamp) {
        timeMap[key].insert(make_pair(timestamp, value));
    }
    
    string get(string key, int timestamp) {
        if(timeMap.find(key) == timeMap.end()) {
            return  "";
        }
        
        auto value = timeMap[key].lower_bound(make_pair(timestamp, ""));

        if(value->first == timestamp) {
            return value->second;
        }
        
        else {
            if(value == timeMap[key].begin()) {
                return "";
            }
            else {
                auto prev_value = prev(value);
                return prev_value->second;
            }
        }
    }
};

 

vector를 사용한 풀이

평소에는 Binary Search를 할 때는 정렬을 해야하나 여기서는 조건에 의하여 timestamp가 증가하여 삽입된다고 하기 때문에 별도의 정렬을 할 필요도 없고, set과도 성능 차이가 없다.

난 그것도 안 읽어서 정렬을 하는 바람에 시간 초과가 발생했다... 문제를 잘 읽자!

class TimeMap {
public:
    unordered_map<string, vector<pair<int, string>>> timeMap;
    TimeMap() {
        timeMap.clear();
    }
    
    void set(string key, string value, int timestamp) {
        timeMap[key].push_back(make_pair(timestamp, value));
    }
    
    string get(string key, int timestamp) {

        // sort(timeMap[key].begin(), timeMap[key].end());
    
        int size = timeMap[key].size();
        int left = 0;
        int right = size - 1;
        string result = "";
        
        while(left <= right) {
            int mid = (left + right) / 2;
            if(timeMap[key][mid].first <= timestamp) {
                result = timeMap[key][mid].second;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return result;
    }
};