[ leetcode ] 146. LRU Cache

해당 문제는 LRU Cache의 put/get동작을 직접 구현하는 문제로 LRU란 Least Recently Used원칙으로 cache를 유지하는 규칙을 뜻합니다. 즉 cache의 capacity가 가득 찼을 때 put일 들어오면, 가장 최근에 접근하지 않은 content를 삭제하고, 최근에 접근한 것들의 우선순위를 높이는 방식입니다. (새로 추가되면 가장 우선순위가 높음)

 

Linked List와 hash table을 활용하여 구현하였습니다. Linked List의 head, tail을 사용하여 가장 최근에 사용한 content를 head에 두고, 우선순위가 가장 낮은 것은 tail에 있습니다.

double linked list로 구현하여 hash table에 (key, node)로 저장해두어 key로 node를 찾고 해당 node를 바로 linked list에서 제거하기에는 double linked list를 사용해야 해당 노드를 삭제하더라도 앞 뒤 노드를 이어줄 수 있었습니다.

 

linked list를 순회하지 않고 node에 가장 빠르게 접근하기 위해 hash_table을 사용했고, double linked list로 O(1)연산으로 삭제가 가능하도록 구현하였습니다.

우선순위를 높일 때도 마찬가지로 O(1)에 삭제하고 바로 head로 삽입하였습니다.

#include <unordered_map>

struct Node {
    int key;
    int val;
    Node* prev;
    Node* next;
    Node(): next(NULL), prev(NULL) {}
    Node(int key, int val) : key(key), val(val), prev(NULL), next(NULL) {}
};

class LRUCache {
public:
    Node* head = new Node();
    Node* tail = new Node();
    unordered_map<int, Node*> hash_table;
    int max_size;

    LRUCache(int capacity) {
        max_size = capacity;
        head->next = tail;
        tail->prev = head;
        hash_table.clear();
    }
    
    void del(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void push_head(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    int get(int key) {
        unordered_map<int, Node*>::iterator it = hash_table.find(key);
        if (it != hash_table.end()) {
            del(it->second);
            push_head(it->second);
            return it->second->val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        unordered_map<int, Node*>::iterator it = hash_table.find(key);
        if (it != hash_table.end()) {
            del(it->second);
        }
        else if (max_size == hash_table.size()) {
            hash_table.erase(tail->prev->key);
            del(tail->prev);
        }
        Node* new_node = new Node(key, value);
        hash_table[key] = new_node;
        push_head(new_node);
    }
};

/**
 * 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);
 */