[LinkedList][Medium] 146. LRU Cache

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

 

LRU Cache를 구현하라.

 

LRU Cache 구현의 핵심은, 

list를 이용하여, 가장 최근에 사용한 데이터를 list의 제일 앞쪽에 위치시키고, 

따라서 capacity가 꽉 차면 가장 마지막에 data를 삭제하는 것이다. 

이때 데이터 접근에 따라 list에서 해당 데이터를 찾고 앞쪽에 위치시켜야 하는데, 

이 검색시간을 O(1)로 하는게 문제 풀이의 핵심이라 할 수 있다. 

 

결국 list의 iterator를 이용해 한번에 지워야 한다. 

 

코드 

class LRUCache {
    int _capacity;
    list<pair<int, int>> _listData;						        // value, key.
    unordered_map<int, list<pair<int, int>>::iterator> _mapData;// key, iterator

public:
    LRUCache(int capacity) : 
        _capacity(capacity)
    {
    }

    int get(int key) 
    {
        auto iter = _mapData.find(key);
        if (iter == _mapData.end())
            return -1;

       // int key = iter->first;
        auto listIter = iter->second;
        int value = listIter->first;

        // move to front. 
        _listData.erase(listIter);
        _listData.push_front(make_pair(value, key));
        _mapData[key] = _listData.begin();
        return value;  
    }

    void put(int key, int val) 
    {
        auto iter = _mapData.find(key);
        if (iter == _mapData.end())
        {
            // add.
            if (_capacity == _listData.size())
            {
                // remove last. 
                int remKey = _listData.rbegin()->second;
                _listData.pop_back();
                _mapData.erase(remKey);
            }

            _listData.push_front(make_pair(val, key));
            _mapData[key] = _listData.begin();
        }
        else
        {
            // update.
            auto listIter = _mapData[key];
            _listData.erase(listIter);

            _listData.push_front(make_pair(val, key));
            _mapData[key] = _listData.begin();
        }
    }
};

 

 

결과

 

Note : 이 알고리즘 풀이는 여기저기 너무 많이 나온다. 꼭 알아 둘 필요가 있다.