Leetcode - 146. LRU Cache 풀이

문제

다음 동작을 하는 LRUCache class 를 구현하라.

• LRUCache(int capacity)
  주어진 capacity값까지만 저장가능. 양수값으로 초기화된다.

• int get(int key)
  key가존재하면 value를 리턴하고 없다면 -1을 리턴.

• void put(int key, int value)
  key가존재하면 value업데이트, 그렇지 않으면 key-value를추가. 만약 key갯수가capacity를초과하면 가장 나중에 사용했던 key를제거.

• get() 또는 put()으로 사용된 key는 가장 최근 사용된 key라는 의미.

• get()과 put()의 시간복잡도는 O(1) 이어야 한다.

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

해결 아이디어

• key-value를가지는 Node클래스를 생성하고 이를 더블링크드 리스트로 연결한다. get() put()으로 호출되거나 추가된 key는 링크드리스트의 맨 마지막으로 이동시킨다. 그러면 head에 가까운 노드가 가장 나중에 사용된 key가 된다.
• 따라서 capacity 초과시 노드의 삭제는 head->next를제거하면 되기 때문에 O(1)이되고, 값을 추가하는것도 tail 앞에 추가하면 되기 때문에 O(1) 이된다.
• key값에 대한 Node의 포인터를 value로 갖는 hashtable을 생성하면 해당 노드의 접근은 O(1)에 가능 하다.

풀이

class LRUCache {
public:
    class Node {
    public:
        int val;
        int key;
        Node *next;
        Node *prev;
        
        Node(int key, int value) {
            this->key = key;
            this->val = value;
            this->next = NULL;
            this->prev = NULL;
        }
    };
    void add_node(Node *prev_node, Node *new_node) {
        // prev -> new -> n
        new_node->next = prev_node->next;
        new_node->prev = prev_node;
        prev_node->next->prev = new_node;
        prev_node->next = new_node;
        
    }
    void del_node(Node *node) {
        // prev -> tgt -> n
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    unordered_map<int, Node *> map; // key -> Node ptr
    Node *head;
    Node *tail;
    int capa;
    int nr_nodes;
        
    LRUCache(int capacity) {
        head = new Node(-1, -1);
        tail = new Node(-2, -2);
        head->next = tail;
        tail->prev = head;
        capa = capacity;
        nr_nodes = 0;
    }
    
    int get(int key) {
        if (map.find(key) == map.end()) {
            return -1;
        }
        del_node(map[key]);
        add_node(tail->prev, map[key]);
        return map[key]->val;
    }
    
    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            map[key]->val = value;
            del_node(map[key]);
            add_node(tail->prev, map[key]);
            return;
        }
        Node *newnode = new Node(key, value);
        add_node(tail->prev, newnode);
        map[key] = newnode;//
        nr_nodes++;
        
        if (nr_nodes > capa) {
            Node *del_tgt = head->next;
            map.erase(del_tgt->key);
            del_node(del_tgt);
            delete del_tgt;
            nr_nodes--;
        }
    }
};