[LeetCode] 146. LRU Cache

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

LRU Cache - LeetCode

 

문제 접근법 : LRU cache 문제인데

os 공부하셨다면 LRU 페이지 교체는 동작 방법은 아실거라 생각합니다.

단 내부구현을 만드는것은 배웠는지 안배웠는진 모르겠으나

저또한 내부구현까지는 배운적이없어서 이기회에 만들게 됐네요

 

처음에 DEQUE와 HASHMAP 을 이용해서 구현할까 했는데 문제조건에 모든 연산이 O(1) 이 되도록 만들라고 되어있어서

GET, PUT 을 어떻게든 O(1)로 만들 생각을하니

평소에 쓰는 자료구조 vector나 deque로는 get연산에서 안나오더군요

 

예를들어  lru 알고리즘에서 사이즈가 3인 lru라할때 1,2,3,2

일때 1 ,2 ,3 에서

1,3,2 가 되어야 lru 페이지 교체에서 빠르게 작동할텐데 

deque로는 put할때마다 인덱스가 계속 변하니 인덱스를 저장해도 소용이 없더군요

 

2가 있는자리만 쏙빼서 결합후 3뒤에 오게 하는 방법이 뭐가있을까?

생각했더니 포인터더군요 list를 이용해서 해당포인터만 저장한다면 빼는것과 뒤에다 결합시키는것이 O(1)만에 작동이 가능하니 list와 unordered_map 을 이용해서 list의 iterator를 가지고있으면 언제든지 O(1)만에 만들수 있습니다.

 

소스코드 : 

class LRUCache{
public:
    unordered_map<int, pair<list<int>::iterator, int>> lru;
    list<int> l;
    int capacity;

    LRUCache(int capacity)
    {
        lru.clear();
        l.clear();
        this->capacity = capacity;
    }

    int get(int key)
    {
        if (lru.count(key) == 0)
            return -1;

        auto a = lru[key].first;//해당 포인터를 가져옴
        int value = lru[key].second;
        //
        l.erase(a);//해당 포인터를 가리키는 노드를 제거하구
        l.push_back(key);//key값만 뒤에저장
        lru[key] = {prev(l.end()), value};//key값에 포인터만 바꿔도됨
        return value;
    }

    void put(int key, int value)
    {
        if (lru.count(key))//key값에있는 value만 바꾸고싶은거뿐
        {
            //그러나 참조했으니 해당 참조했으면 가장 빠르게 참조했다는걸 가르켜야하니 get알고리즘을 했던것과 중복
            get(key);
            lru[key].second = value;//포인터까지 이미 변경되어있을테니 값만 변경하면됨
        }
        else
        {
            if (l.size() >= capacity)
            {
                int bk = l.front();
                lru.erase(bk);
                l.pop_front();
            }
            l.push_back(key);
            lru[key] = {prev(l.end()), value};
        }
    }
};

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.