LeetCode - 146. LRU Cache

처음에는 vector와 해시맵을 사용해서 구현했다.

vector에는 key들을 우선순위 순서대로 넣고(우선순위 높은 게 앞으로),

해시맵에는 해당 key에 대한 value를 저장했다.

class LRUCache {
public:
    int cap;
    vector<int> cache_key;
    unordered_map<int, int> cache_map;

    LRUCache(int capacity) {
        this->cap = capacity;
    }
    
    int get(int key) {
        //get한 key 우선순위 높이기
        auto it = find(cache_key.begin(), cache_key.end(), key);
        if (it == cache_key.end())
            return -1;
        cache_key.erase(it);
        cache_key.insert(cache_key.begin(), key);
        return cache_map[key];
    }
    
    void put(int key, int value) {
        //cache가 꽉 차고, 해당 key가 없을 때
        auto it = find(cache_key.begin(), cache_key.end(), key);
        if (cache_key.size() == cap && it == cache_key.end()) {
            int tmp = cache_key.back();
            cache_key.pop_back();
            cache_map.erase(tmp);
        }
        //cache에 자리가 있을 때
        //cache에 해당 값이 있을 때
        else if (it != cache_key.end()) {
            cache_key.erase(it);
        }
        cache_map[key] = value;
        cache_key.insert(cache_key.begin(), key);
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

엄~청나게 오래 걸렸다.

 

그래서 이번에도 해설 참고.

vector가 아니라 doubly linked list를 사용해서 node를 빨리 삭제, 삽입하도록 했다.(우선순위 역순. tail이 제일 우선순위 높음)

그리고 해당 노드의 위치는 해시맵을 사용해서 저장했다. 해시맵의 key가 문제에서 주어지는 key이고, 해시맵의 value는 해당 key값을 가진 node의 포인터.

Doubly Linked List에 (key,value)를 put할 때는, 먼저 key가 있는지 확인 후 있으면 해당 key에 대한 value 업데이트. 그리고 해당 node를 DLL에서 삭제 후 맨 뒤에 삽입.

key가 없으면 새로운 node 생성해서 key, value 입력. 그리고 해당 node DLL에 삽입.

 

궁금해서 찾아봤더니 실제 OS에서도 LRU Cache를 Double Linked List와 해시 테이블을 사용해서 구현한다고 한다.

 

Key Idea

빠른 삽입, 삭제-> Doubly linked list

빠른 탐색 -> 해시맵