[LeetCode] LRU Cache (C++)

문제 링크: https://leetcode.com/problems/lru-cache/description/

LRU Cache - LeetCode

1. 주의할 점

- DoubleLinkedList와 HashMap을 사용 및 구현 할 줄 알아야 한다

- key에 매칭되는 Node가 어디에 위치해 있는지 순차적으로 탐색하여 O(N)에 찾도록 구현하지 않는다

- 신경써야 하는 부분이 많은 만큼 주석을 통해 나타내면 구현하면서도 헷갈리지 않는다

 

2. 구현

- LRUCahce에서 사용할 DoubleLinkedList의 원소가 될 Node를 만든다

- LRUCache 크기를 저장할 변수와 현재 만들어진 Node수를 저장할 변수를 만든다

- get() 함수를 수행할 때 Map에 없는 키라면 -1을 반환한다. 있는 Key라면 moveKey() 함수를 통해 가장 최근에 사용된 상태로 갱신하고 value를 반환한다. 이때, 찾고자하는 Node가 Root/Tail/중간의 Node인지에 따라 조건이 다르므로 유의한다

- put() 함수를 수행할 때 Map에 있는 키라면 위와 같이 갱신한다. 만약 없던 키라면 Root앞에 배치하고 Root를 갱신한다. 그리고 캐시의 크기가 처음에 지정한 값보다 크다면 Tail 노드를 삭제하고 Map에서도 삭제한다.

class LRUCache {
    struct Node{
        int val;
        Node *left;
        Node *right;

        Node(int _val){
            val = _val;
            left = NULL;
            right = NULL;
        }
    };
public:
    Node* root;
    map<int,Node*> keyToNode;
    map<Node*,int> nodeToKey;
    int len, maxLen;

    LRUCache(int capacity) {
        len = 0;
        maxLen = capacity;
        root = NULL;    
    }
    
    int get(int key) {
        //찾는다
        if(keyToNode.find(key)==keyToNode.end()) return -1;

        //최신 상태로 바꾼다
        Node* node = keyToNode[key];
        moveKey(node);

        return node->val;
    }
    
    //left가 오래된것, right가 최신
    void put(int key, int value) {
        //이미 있던 값인지 확인
        if(keyToNode.find(key)==keyToNode.end()){
            //새롭게 추가
            Node* node = new Node(value);
            if(root==nullptr){
                root = node;
                len++;
            }
            else{
                root->right = node;
                node->left = root;

                //root 갱신
                root = node;

                //캐시가 꽉 찼는지 확인
                if(len==maxLen){
                    Node* head = root;
                    while(head->left!=nullptr){
                        head = head->left;
                    }
                    head->right->left = nullptr;
                    int keyVal = nodeToKey[head];
                    nodeToKey.erase(head);
                    keyToNode.erase(keyVal);
                }
                else len++;
            }
            //map에 추가
            keyToNode[key] = node;
            nodeToKey[node] = key;
        }
        //이미 있던 경우
        else{
            Node* node = keyToNode[key];
            moveKey(node);

            //map 갱신
            node->val = value;
            keyToNode[key] = node;
        }
    }

    void moveKey(Node* node){
        Node* recentCalledNode = node->right;
        Node* lateCalledNode = node->left;

        //루트라면 그대로 둔다
        if(recentCalledNode==nullptr){
            //root
        }
        else{
            //꼬리인 경우
            if(lateCalledNode==nullptr){
                recentCalledNode->left = nullptr;
            }
            else{
                lateCalledNode -> right = recentCalledNode;
                recentCalledNode -> left = lateCalledNode;
            }
            node->right = nullptr;
            node->left = root;
            root->right = node;

            //root 갱신
            root = node;
        }
    }
};