알고리즘/[ LeetCode ]

[ LeetCode ][JAVA][146] LRU Cache

kim.svadoz 2021. 5. 11. 22:02
반응형

leetcode.com/problems/lru-cache/

 

LRU Cache - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

문제

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 LinkedListHashMap을 이용해 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;

        }
    }
}
반응형