[ LeetCode ][JAVA][146] LRU Cache

leetcode.com/problems/lru-cache/

LRU Cache - LeetCode

문제

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.

Follow up:
Could you do get and put in O(1) time complexity?

예시

# 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

접근

get() 메소드와 put() 메소드를 O(1)의 Complexity로 구현해야 한다.

따라서 Doubly LinkedList 와 HashMap을 이용해 LRU Cache를 구현한다.

어려운 점은 삽입, 삭제시 연결리스트의 head와 tail을 올바르게 처리하는 작업이다.

최근 K사 테스트에서 비슷한 문제가 나왔기 때문에 확실히 익혀두자.

코드

class LRUCache {
    // 시간복잡도 : O(1);
    // doubly linked list + HashMap !!
    public class CacheItem {
        int key;
        int value;
        CacheItem prev;
        CacheItem next;
        public CacheItem(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    CacheItem head;
    CacheItem tail;
    int capacity;
    Map<Integer, CacheItem> map;

    public LRUCache(int capacity) {
        // 생성자
        head = null;
        tail = null;
        this.capacity = capacity;
        map = new HashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            CacheItem cur = map.get(key);

            // head 포인터를 바꿔주어야 한다.
            if (cur != head) {
                if (cur == tail) {
                    // move tail to one in front
                    tail = tail.prev;
                }

                // move cur to head
                //    head .... cur.prev > cur > cur.next
                // => cur-head .... cur.prev > cur.next 
                if (cur.prev != null) cur.prev.next = cur.next;
                if (cur.next != null) cur.next.prev = cur.prev;
                cur.next = head;
                head.prev = cur;
                cur.prev = null;
                head = cur;
            }

            return cur.value;
        }
    }

    public void put(int key, int value) {
        if (get(key) == -1) {
            // insert
            CacheItem cur = new CacheItem(key, value);

            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                // head .....
                // cur > head .....
                cur.next = head;
                head.prev = cur;
                head = cur;
            }

            map.put(key, cur);

            if (map.size() > capacity) {
                // evict tail
                // ..... tail.prev > tail
                // ..... tail.prev
                map.remove(tail.key);
                tail.prev.next = null;
                tail = tail.prev;
            }
        } else {
            // update
            map.get(key).value = value;

        }
    }
}