[리트코드/자바] 146. LRU Cache

요즘 리트코드를 꾸준히 풀려 버릇하고 있습니다. 친구의 소개로 흥미로운 문제가 있어 고전하며 풀이에 성공하였네요. 혹, 나중에 비슷한 문제가 나올때 복기하기 위해서 알고리즘 문제풀이를 하나씩 남겨보려고 합니다.

해당 문제는 리트코드 홈페이지(이곳)에서 확인할 수 있습니다.

 

LRU Cache

아래의 조건을 만족하는 자료구조를 설계하세요.

 

LRU Cache class를 구현하세요.

• 메소드 구현 - LRUCache(int capacity)
  LRU 캐시를 양수 크기만큼 생성하여 초기화합니다.
• 메소드 구현 - int get(int key)
  key에 해당하는 value가 존재한다면 해당 value를 반환하고, 그렇지 않다면 -1을 반환합니다.
• 메소드 구현 - void put(int key, int value)
  key-value쌍을 캐시에 추가하며, 캐시 용량을 초과한다면 최근에 가장 적게 사용된 key를 제거합니다.
  만약, key가 이미 존재한다면 새로운 value로 업데이트합니다.
• get(), put()은 반드시 O(1)의 시간복잡도에 실행되어야 합니다.

 

풀이

기본적으로 이 문제는 HashMap을 사용하여 key-value형식으로 데이터를 저장하는 자료구조를 구현해야 한다.

주목해야할 점은 최근 가장 적게 사용된(Least Recent Used) 값을 기억하기 위해 HashMap 이외 다른 자료구조를 추가로 구현해서 사용해야한다는 점이다.

 

Array 사용하기

Array를 사용해서 가장 최근에 사용된 key를 index 0에 위치하게 하여 key 사용이력을 관리할 수 있다.

여기서 문제는 key가 사용되거나 새로운 key가 삽입되는 등 변동이 생길때마다 모든 배열 원소를 오른쪽으로 shift해야한다. 즉, O(n)의 시간이 소요된다. 또한, 변동이 생긴 원소를 찾기위해서는 모든 배열원소를 순회하며 탐색해야한다. Array와 유사한 Stack이나 Queue를 생각해봤지만, 결국 해당하는 원소를 찾기 위해서는 순회해야한다는 불편함이 존재한다.

 

LinkedList 사용하기

LinkedList 중 시작(head)와 끝(Tail)을 함께 저장하는 Double Linked List를 사용하면 O(1)의 시간복잡도로 모든 작업을 수행할 수 있다. HashMap과 그에 해당하는 리스트를 그림으로 표현하면 다음과 같다.

새로운 key가 들어오거나 마지막 key를 삭제하기위해서 head와 tail노드를 이용하면 즉시 해당 노드에 접근할 수 있다. 조금 더 설명하자면, 새로운 key가 삽입된 경우, head의 다음 노드에 새로운 key 노드를 추가하면 된다. 최근에 가장 사용이 적은(LRU) key를 삭제하기 위해서는 tail 이전의 노드에 접근하면 된다.

 

💡 그렇다면, 이미 리스트에 존재하는 key를 다시 사용하거나 value값만 변경된 경우, 리스트에 이미 존재하는 key의 위치를 어떻게 찾아야하나?

 

특정 key를 찾기 위해서 리스트의 head와 tail까지 모두 순회한다면, 최악의 경우엔 결국 O(n)의 시간이 소요된다.

이를 해결하기 위해서, HashMap의 구조를 변경해볼 수 있다. key와 value, value를 지닌 노드를 구성하는 HashMap을 설계하면 다음과 같이 표현할 수 있다.

💡문제의 조건에서 주의할점은 put() 또는 get()메소드 둘 다 key를 사용한것이므로 key 사용내역에 변동을 줄 수 있다.

 

코드구현은 다음과 같다.

class LRUCache {

        final private int maxCapacity;
        private final HashMap<Integer, Node> cache; // store key & key-value Node
        private final DoubleLinkedList frequency; // store key history

        public static class DoubleLinkedList {

            public int size = 0;
            public Node head;
            public Node tail;

            // init DoubleLinked List with empty head and tail Node
            public DoubleLinkedList() {
                this.head = new Node(null, null);
                this.tail = new Node(null, null);

                this.head.next = this.tail;
                this.head.prev = this.tail;

                this.tail.next = this.head;
                this.tail.prev = this.head;
            }

            /**
             * add new node on head's next position
             * @param newNode
             */
            public void insert(Node newNode) {

                Node secNode = this.head.next;
                this.head.next = newNode;
                newNode.next = secNode;
                secNode.prev = newNode;
                newNode.prev = this.head;
                size++;
            }

            /**
             * remove last node in frequency list
             * @return
             */
            public Node cutoff() {
                Node target = this.tail.prev;
                Node end = target.prev;
                end.next = this.tail;
                this.tail.prev = end;
                size--;
                return target;
            }

            public void iterate() {
                if(size==0) {
                    System.out.println("EMPTY");
                } else {
                    Node cursor = this.head.next;
                    while(!cursor.equals(this.tail)) {
                        System.out.print("{"+cursor.key+":"+cursor.value+"} ");
                        cursor = cursor.next;
                    }
                }
                System.out.println();

            }

        }

        public static class Node {
            private Integer key;
            private Integer value;
            private Node next;
            private Node prev;

            public Node(Integer key, Integer value) {
                this.key = key;
                this.value = value;
            }

            public String toString() {
                return "{"+this.key+":"+this.value+"}";
            }
        }

        /**
         * initialize LRU cache with positive size capacity
         * @param capacity
         */
        public LRUCache(int capacity) {
            if(capacity < 1) {
                throw new IllegalArgumentException("Invalid input");
            } else {
                this.cache = new HashMap<>();
                this.frequency = new DoubleLinkedList();
                this.maxCapacity = capacity;
            }
        }



        /**
         * Update value of key if key exists.
         * Otherwise, add key-value pair to cache.
         * If number of keys exceeds capacity from this operation, evict the least recently used key.
         * @param key
         * @param value
         */
        public void put(int key, int value) {

            if(cache.containsKey(key) || cache.keySet().size() < this.maxCapacity) {
                // when cache is not full
                if(cache.containsKey(key)) {
                    cache.get(key).value = value;
                    update(cache.get(key));
                    frequency.head.next.value = value;
                } else {
                    Node newNode = new Node(key, value);
                    cache.put(key, newNode);
                    frequency.insert(newNode);
                }

            } else {
                // when the cache capacity is full
                Node deletedNode = frequency.cutoff();
                cache.remove(deletedNode.key);

                // store new key-value pair on map and update frequency map
                Node newNode = new Node(key, value);
                cache.put(key, newNode);
                frequency.insert(newNode);

            }
        }

        /**
         * update the most recent used node in frequency list with most front node
         * @param target
         */
        public void update(Node target) {
            if(this.frequency.size > 1) {

                Node front = this.frequency.head.next;

                if(target.key != front.key) {

                    target.prev.next = target.next;
                    target.next.prev = target.prev;

                    this.frequency.insert(target);
                }
            }
        }

        /**
         * return value of key if key exists, otherwise return -1
         * @param key
         * @return
         */
        public int get(int key) {
            if(cache.containsKey(key)) {
                update(cache.get(key));
                return cache.get(key).value;
            } else {
                return -1;
            }
        }
    }

 

보완해야할 점이나 잘못된 부분은 덧글로 알려주시면 다시 고민해서 풀어보겠습니다🤔