LRU Cache [Final 기출] (Hash Table,Linked List,Design,Doubly-Linked List)

https://leetcode.com/problems/lru-cache/description/

DBMS Buffer에 Data를 Replace 하는 대표적인 Algorithm 중 하나인 LRU 방법에 대해 Implementation을 해보는 실습을 해본다.

 

문제 Description은 아래와 같다.

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

 

Example 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

 

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

위 문제에선 O(1)로 구현하라고 하지만, 그것은 Hash-map을 써야 가능한 얘기다.

필자는 Doubly linked list를 연습하고 싶기에 O(N)을 감안하고, test case 몇 개를 설정해서 문제를 풀어나가보려 한다.

 

1. Python

기본 뼈대 코드는 아래와 같다.

class LRUCache:

    def __init__(self, capacity: int):
        

    def get(self, key: int) -> int:
        

    def put(self, key: int, value: int) -> None:
        
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

 

해당 class 만으론 Doubly linked list 사용이 어려우니, Node class도 만들어준다.

 

계속 test case에서 error가 뜨길래 또 시간낭비좀 했다.

 

미안하지만,, 부끄럽지만 또 LLM의 도움을 받았다.

 

결론은 Node를 Update할 때 doubly linked list인만큼 항상 Node 별 prev / next를 모두 update 해줘야 한다는 것이다.

 

이걸 놓치니까 계속 Error가 뜨지...

 

아래 fixed 부분이 내가 해매다가 힌트를 보고 수정한 것이다.

 

class Node:
    def __init__(self,key:int,value:int,prev=None,next=None):
        self.key = key
        self.value = value
        self.prev = prev
        self.next = next
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.head = None
        self.tail = None

    def get(self, key: int) -> int:
        temp = self.head
        while temp:
            if temp.key == key: # update temp node to self.head
                # temp : head
                if not temp.prev:
                    return temp.value
                # temp : tail
                if not temp.next:
                    self.tail = temp.prev
                    self.tail.next = None
                    temp.prev = None
                    temp.next = self.head
                    self.head.prev = temp # fixed 
                    self.head = temp
                    return temp.value
                # temp in the middle of the nodes
                temp.prev.next = temp.next
                temp.next.prev = temp.prev
                temp.prev = None
                temp.next = self.head
                self.head.prev = temp # fixed
                self.head = temp
                return temp.value
            temp = temp.next
        return -1

    def put(self, key: int, value: int) -> None:
        # capa >= 1
        # No head and tail
        new_node = Node(key,value)
        if not self.head :
            self.head = new_node
            self.tail = new_node
            self.size += 1
            return
        # Yes head and tail, try update key first
        temp = self.head
        while temp:
            # Update case
            if temp.key == key:
                temp.value = value
                #fixed -> update the node even if its already exist
                if temp != self.head:
                    if temp == self.tail:
                        self.tail = self.tail.prev
                        self.tail.next = None
                    else:
                        temp.prev.next = temp.next
                        temp.next.prev = temp.prev
                    temp.prev = None
                    temp.next = self.head
                    self.head.prev = temp
                    self.head = temp
                return
            temp = temp.next
        # size < capa case, add new_node -> head
        if self.size < self.capacity:
            new_node.next = self.head
            self.head.prev = new_node
            self.head= new_node
            self.size += 1
            return
        # size == capa case, delete tail and add new_node ->head
        else:
            # add head
            new_node.next = self.head
            self.head.prev = new_node
            self.head= new_node
            # delete tail
            self.tail = self.tail.prev
            self.tail.next = None

            return            

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Leetcode 상으론 O(1)를 구현하지 못해 탈락이지만 I dont care ~

 

알쏭 달쏭한 Doubly linked list의 세계..

 

이건 비단 이것뿐만 아니라 추후 linked list를 이용한 graph / tree 문제에서도 왕왕 발생할 수 있는 문제이니 항상 연결관계를 잘 파악하고 있읍시다.

 

C는 건너뛰고 C++로도 한 번 구현해보겠다.

 

2. C++

기본 뼈대 코드는 아래와 같다.

class LRUCache {
public:
    LRUCache(int capacity) {
        
    }
    
    int get(int key) {
        
    }
    
    void put(int key, int value) {
        
    }
};
/**
 * 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);
 */

 

역시나 Doudlbly linked list 사용을 위해서 Node class를 만들어주겠다.

 

비슷한 맥락으로 만들었다.

 

class Node{
public:
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int k, int v):key(k),value(v){
        prev = nullptr;
        next = nullptr;
    }
};

class LRUCache {
public:
    Node* head;
    Node* tail;
    int capacity;
    int size;
    LRUCache(int capacity):capacity(capacity),size(0){
        head = nullptr;
        tail = nullptr;
    }
    
    int get(int key) {
        Node* temp = head;
        while(temp){
            if(temp->key == key){
                // update finded node
                if(temp != head){
                    if(temp == tail){
                        tail = temp->prev;
                        tail->next = nullptr;
                    }else{
                        temp->prev->next = temp->next;
                        temp->next->prev = temp->prev;
                    }
                    temp->prev = nullptr;
                    temp->next = head;
                    head->prev = temp;
                    head = temp;
                }
                return temp->value;
            }
            temp = temp->next;
        }
        return -1;
    }
    
    void put(int key, int value) {
        Node* new_node = new Node(key,value);
        // No head & tail
        if(!head){
            head = new_node;
            tail = new_node;
            size++;
            return;
        }
        // Try update exist key
        Node* temp = head;
        while(temp){
            // find case , update it
            if(temp->key==key){
                temp->value = value;
                // move it to the head
                if(temp != head){
                    if(temp == tail){
                        tail = temp->prev;
                        tail->next = nullptr;
                    }else{
                        temp->prev->next = temp->next;
                        temp->next->prev = temp->prev;
                    }
                    temp->prev = nullptr;
                    temp->next = head;
                    head->prev = temp;
                    head = temp;
                }
                return;
            }
            temp = temp->next;
        }
        // fail to update, now add new node
        if(size < capacity){
            new_node -> next = head;
            head->prev = new_node;
            head = new_node;
            size++;
            return;
        }
        else{//size == capa
            new_node -> next = head;
            head->prev = new_node;
            head = new_node;
            // delete tail
            Node* temp = tail;
            tail = tail->prev;
            tail->next = nullptr;
            temp->prev = nullptr;
            delete temp;
        }
    }
};

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

 

겁나리 길고 복잡해보이지만, 사실 알고보면 그닥 빡세진 않다.

 

근데 이게 솔루션을 보고 문제를 푸는 케이스라 이러지..

 

실전에서도 이런 문제를 맞닥뜨렸을 때 과감하게 풀 수 있는 용기와 지혜가 있었으면 좋겠당!!!!!!!