146. LRU Cache

Intuition

• public LRUCache(int capacity): LRU cache 구현

  • 문제를 푸는 메인 메서드
  • capacity: Cache의 용량
  • lRUCache.put(key, value)를 했을 때,

• public void put(int key, int value): 캐시에 값 넣기

  • 캐시에 있는 거 -> 다시 최신 순위로 변경

• public int get(int key): 캐시에서 값 얻기

  • 얻을 때 값 최신 순위로 변경
  • 값을 최신 순위로 변경하면서 값 반환

Approach

1. put(index, node) 호출
   1. HashMap으로 확인했을 때, Cache에 없는 값인 경우
      • HashMap에 값 추가
      • Linked List 맨 앞 순서에 값 추가
      • 동시에 capacity를 초과하면 맨 마지막에 있는 값 삭제
   2. HashMap으로 확인했을 때, Cache에 있는 값인 경우
      • HashMap의 index 값 갱신
      • Linked List에서 해당 인덱스로 위치를 찾은 후, 맨 앞으로 이동
2. get(key) 호출
   - Linked List에서 해당 인덱스로 위치를 찾은 후, 맨 앞으로 이동
   - 해당 값 반환

Complexity

• Time complexity: O(1)
• Space complexity: O(n)

Code

// import java.util.LinkedList;
class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    private HashMap<Integer, Node> cacheMap;
    private int capacity;
    private Node node;
    private Node head;
    private Node tail;


    // 이것을 구현...
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cacheMap = new HashMap<>();

        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }
    
    // key가 존재하면 값 반환, 없으면 -1 반환
    public int get(int key) {
        if(!cacheMap.containsKey(key)){
            return -1;
        }
        Node node = cacheMap.get(key);
        toFirst(node);
        return node.value;
    }
    
    // 값을 넣기 
    public void put(int key, int value) {
        if (cacheMap.containsKey(key)){ // 이미 있는 경우
            Node node = cacheMap.get(key);
            node.value = value;
            toFirst(node);
        }else{
            if (cacheMap.size() >= capacity){
                cheOldNode(node);
            }
            Node newNode = new Node(key, value);
            cacheMap.put(key, newNode);
            push2First(newNode);
        }
    }

    public void toFirst(Node node){ // 기존 노드 위치에서 삭제하고 이동
        delNode(node);
        push2First(node);
    }
    public void push2First(Node node){ // 노드 앞으로 이동 
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public void delNode(Node node){ // 원래 위치에서 노드 삭제
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void cheOldNode(Node node){ // 오래된 노드 삭제 (Map에서도)
        cacheMap.remove(tail.prev.key);
        delNode(tail.prev);
    }

}

여담 및 자료

Doubly Linked List 선택 및 구현

• Doubly Linked List란?
  Linked List와 비슷하지만, 앞 뒤 연결관계가 모두 있는 자료형이에요. 예전에 풀었던 21. Merge Two Sorted Lists 와 비슷한 자료형! (그때는 한 문제 푸는 데 5시간 걸렸는데.... 뭔가 감동) 주요 특징으로는 O(1)로 데이터 조작이 가능해요.
• 주요 참고 자료
  • Doubly LinkedList (이중 연결리스트) 구현하기
  • LinkedHashMap 사용법 및 예제
  • GPT의 도움....

여담

• Doubly Linked List를 사용해야 하는 이유
  • 문제의 조건에도 있지만, 모든 위치에서 시간복잡도를 O(1)로 실행하려면 Doubly Linked List를 사용하는 게 좋겠더라고요
• 처음에는 LRU 캐시에 관해 다시 알아보면서 Doubly Linked List를 구현하는 방향으로 가닥을 잡았었는데, 뒤늦게 LinkedHashMap과 구현 방향이 거의 똑같다는 걸 알았어요. 지금까지 찾은 게 아까워서 그냥 그대로 직접 만들어보았습니다....