146. LRU Cache

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

 

 

Q. LRU cache를 사용하도록 class를 디자인 하라. 

 입력은, key, value의 두개의 int type이 들어오며, key가 같으면 overwrite 하고 없으면 add 하라.

 

 

Solution. 

 key를 기준으로 data에 접근해야 하므로, 우선 map 이나 dictionary 타입의 구조가 필요하다. 

그리고,  마지막으로 덜 사용한데이터에 바로 접근해야 하므로, list 구조가 필요하다. 

 

c# 에서는 iterator가 없으므로, 아래와 같이 더블 링크드 리스트를 사용해서 데이터에 바로 접근하면 적당하다. 

public class DoubleListNode 
{
    public int val, key;
    public DoubleListNode next;
    public DoubleListNode prev;
    public DoubleListNode(int x) {
        val = x;
        next = null;
        prev = null;
    }
}

 

 

데이터를 더할 때

 : 데이터가 없으면 -> 노드를 만든다 -> 노드를 헤드로 옮긴다.  ->  capacity를 넘어가면, 끝 노드를 map과 리스트에서 모두 삭제 한다. 

 : 데이터가 있을 때 -> map 으로 노드를 찾아 접근해서 값을 업데이트 한다 -> 해당 노드를 헤드로 옮긴다. 

 

데이터를 반환할 때

 : 데이터가 있으면 -> map으로 노드를 찾아 해당 값을 반환 준비를 한다 -> 해당 노드를 리스트 헤드로 옮긴다. -> 값 반환.

 

위 로직대로 코드를 만든다. 

 

C# version.

public class LRUCache 
{
    public class DoubleListNode 
    {
        public int val, key;
        public DoubleListNode next;
        public DoubleListNode prev;
        public DoubleListNode(int x) {
            val = x;
            next = null;
            prev = null;
        }
    }

    int mCapacity;
    DoubleListNode mHead, mTail;
    Dictionary<int, DoubleListNode> mCacheNodes = new Dictionary<int, DoubleListNode>();   

    // LRU Cache를 구현하라. 
    public LRUCache(int capacity) {
        mCapacity = capacity;
        mHead = new DoubleListNode(0);
        mTail = new DoubleListNode(0);

        mHead.next = mTail;
        mTail.prev = mHead;
    }
    // key가 없으면 -1을 반환한다.
    public int Get(int key) 
    {
        if(mCacheNodes.ContainsKey(key))       
        {
            DoubleListNode node = mCacheNodes[key];
            RemoveNode(node);
            AddNodeToHead(node);
            return node.val;
        }
        else return -1;
    }
    // 더해지는 값이 capacity를 넘어서면, least recent value를 제거한다.
    public void Put(int key, int value) 
    {
        if(mCacheNodes.ContainsKey(key))
        {
            DoubleListNode node = mCacheNodes[key];
            node.val = value;
            RemoveNode(node);
            AddNodeToHead(node);
        }
        else
        {
            // Add. 
            DoubleListNode node = new DoubleListNode(value);
            node.key = key;
            mCacheNodes[key] = node;
            AddNodeToHead(node);

            // Capacity check.
            if(mCacheNodes.Count > mCapacity)
            {
                // remove tail. 
                DoubleListNode back = mTail.prev;
                RemoveNode(back);
                // Console.WriteLine(back.key);
                mCacheNodes.Remove(back.key);
            }
        }
    }

    void RemoveNode(DoubleListNode node)
    {
        node.prev.next = node.next;    
        node.next.prev = node.prev;
    }
    void AddNodeToHead(DoubleListNode node)
    {
        var oldFirst = mHead.next;
        mHead.next = node;
        node.prev = mHead;
        node.next = oldFirst;
        oldFirst.prev = node;
    }
}

 

 

적절한 결과를 얻었다.

 

Note) Head, Tail을 null 로 만들어 값 인풋값과 동기화 하기 보다, 고정으로 두고 사이에 데이터를 넣으면 값 관리가 더 수월하다. 

 

Note) 반드시 알아두면 좋은 복합 문제류다. 꼭 알아두자.

 

 

C++ Version

class LRUCache {
    int _capacity = 0;
	unordered_map<int, list<pair<int, int>>::iterator> _mapData;	// key, iterator to value.
	list<pair<int, int>> _listKeyValues;
public:
    LRUCache(int capacity) : 
        _capacity(capacity)
    {
        _mapData.clear();
	    _listKeyValues.clear();
    }

    int get(int key) {

        unordered_map<int, list<pair<int, int>>::iterator>::iterator itr = _mapData.find(key);
        if (itr != _mapData.end())
        {
            // Move to front. 
            list<pair<int, int>>::iterator target = itr->second;
            int value = target->second;
            _listKeyValues.erase(target);
            _listKeyValues.push_front(make_pair(key, value));
            _mapData[key] = _listKeyValues.begin();

            return value;
        }
        return -1;
    }

    void put(int key, int val) 
    {
        unordered_map<int, list<pair<int, int>>::iterator>::iterator itr = _mapData.find(key);
        if (itr == _mapData.end())
        {
            if (_mapData.size() >= _capacity)
            {
                // delete the last one. 
                list<pair<int, int>>::iterator toDel = _listKeyValues.end();
                --toDel;
                int keyToDelete = (*toDel).first;
                _listKeyValues.pop_back();		// delete the last data.
                _mapData.erase(keyToDelete);	// delete it from map.
            }

            _listKeyValues.push_front(make_pair(key, val));
            _mapData[key] = _listKeyValues.begin();
        }
        else
        {
            list<pair<int, int>>::iterator target = itr->second;
            int value = val;    // update value.
            _listKeyValues.erase(target);
            _listKeyValues.push_front(make_pair(key, value));
            _mapData[key] = _listKeyValues.begin();
        }
    }
};

 

 

C# with LinkedList Collection version. 

public class LRUCache
{
    LinkedList<Tuple<int, int>> _listBuff;
    Dictionary<int, LinkedListNode<Tuple<int, int>>> _dictBuff;
    int _capacity;

    public LRUCache(int capacity) 
    {
        _capacity = capacity;
        _listBuff = new LinkedList<Tuple<int, int>>();
        _dictBuff = new Dictionary<int, LinkedListNode<Tuple<int, int>>>();
    }
    public int Get(int key) 
    { 
        if(_dictBuff.ContainsKey(key))
        {
            var node = _dictBuff[key];
            int ret = node.Value.Item2;

            _listBuff.Remove(node);
            _listBuff.AddFirst(node);
            return ret;
        }
        return -1;
    }

    public void Put(int key, int value) 
    {
        if(_dictBuff.ContainsKey(key))
        {
            var node = _dictBuff[key];
            _listBuff.Remove(node);

            node.Value = new Tuple<int, int>(key, value);
            _listBuff.AddFirst(node);
        }
        else
        {
            if(_dictBuff.Count >= _capacity)
            {
                var tailNode = _listBuff.Last;
                _dictBuff.Remove(tailNode.Value.Item1);
                _listBuff.RemoveLast();
            }

            // add new one. 
            LinkedListNode<Tuple<int, int>> node = new LinkedListNode<Tuple<int, int>>(new Tuple<int, int>(key, value));
            _listBuff.AddFirst(node);
            _dictBuff.Add(key, node);
        }
    }
}