[LeetCode] 146. LRU Cache

146. 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.

The functions get and put must each run in O(1) average time complexity.

LRU(Least Recently Used) 캐시의 제약 조건을 따르는 자료구조를 설계하십시오.

LRUCache 클래스를 구현하십시오:

• LRUCache(int capacity): 양수 크기의 capacity(용량)를 가진 LRU 캐시를 초기화합니다.
• int get(int key): key가 존재하면 해당 값을 반환하고, 존재하지 않으면 -1을 반환합니다.
• void put(int key, int value): key가 존재하면 값을 업데이트합니다. 존재하지 않으면 key-value 쌍을 캐시에 추가합니다. 만약 이 작업으로 인해 키의 개수가 capacity를 초과하면, 가장 오랫동안 사용되지 않은(Least Recently Used) 키를 제거합니다.

get과 put 함수는 각각 평균 $O(1)$의 시간 복잡도로 동작해야 합니다.

 

Example

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

---

1. 문제 요구사항 분석

용량이 정해져 있는 cache에 가장 오래 전에 사용된 값이 가장 먼저 제거되는 LRU Cache 문제

 

2. 접근 전략

😭 Priority Queue: 시간복잡도 O(n) → 문제 요구사항: get과 put 연산 모두 평균 시간 복잡도 O(1)을 만족

 

😁 HashMap + Doubly Linked List

→ 데이터를 조회하거나 추가할 때 해당 노드를 리스트의 맨 앞(Head)으로 옮겨 최근에 사용되었음을 표시하고, 캐시 용량이 꽉 찼을 때는 리스트의 맨 뒤(Tail)에 있는 가장 오래된 노드를 O(1)로 삭제하는 방식으로 LRU 구현

 

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    private Map<Integer, Node> cache = new HashMap<>();
    private int capacity;
    private Node head, tail; // 가짜 머리와 꼬리
	class Node {
	    int key;
	    int value;
	    Node prev; // 내 앞의 노드
	    Node next; // 내 뒤의 노드
	
	    public Node() {}
	    public Node(int key, int value) {
	        this.key = key;
	        this.value = value;
	    }
	}
	
    public LRUCache(int capacity) {
        this.capacity = capacity;
        
        // 가짜 머리와 꼬리를 만들고 서로 연결해 둡니다.
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    
	// 1. 노드를 맨 앞(head 바로 뒤)에 추가하는 메서드 (가장 최근 사용됨)
    private void addNode(Node node) {
        node.prev = head;
        node.next = head.next;
        
        head.next.prev = node;
        head.next = node;
    }

    // 2. 노드를 현재 위치에서 쏙 빼내는 메서드
    private void removeNode(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;
        
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    // 3. 기존 노드를 맨 앞으로 옮기는 메서드 (사용될 때마다 호출)
    private void moveToHead(Node node) {
        removeNode(node); // 원래 자리에서 빼서
        addNode(node);    // 맨 앞으로 붙임
    }

    // 4. 가장 오래된 녀석(tail 바로 앞)을 잘라내고 반환하는 메서드 (용량 꽉 찼을 때)
    private Node popTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
    
    // 데이터 조회
    public int get(int key) {
        Node node = cache.get(key); // 해시맵에서 O(1)로 바로 찾음
        
        if (node == null) {
            return -1; // 없으면 -1 반환
        }
        
        // 찾았으면 "나 방금 쓰였어!" 하고 맨 앞으로 이동
        moveToHead(node); 
        return node.value;
    }

    // 데이터 추가 또는 수정
    public int put(int key, int value) {
        Node node = cache.get(key);

        if (node != null) {
            // 이미 존재하는 키라면 값만 업데이트하고 맨 앞으로 이동
            node.value = value;
            moveToHead(node);
        } else {
            // 새로운 데이터라면 노드 생성
            Node newNode = new Node(key, value);
            cache.put(key, newNode); // 해시맵에 등록
            addNode(newNode);        // 맨 앞에 추가

            // 용량을 초과했다면 가장 오래된 것 삭제
            if (cache.size() > capacity) {
                Node tail = popTail();       // 꼬리에서 싹둑 잘라내고
                cache.remove(tail.key);      // 해시맵에서도 삭제
            }
        }
    }
}