[Java] LeetCode 146: LRU Cache

[문제 바로 가기] - LRU Cache

문제 해석

LRU Cache 클래스를 구현해라.

• LRUCache(int capacity) : capacity를 크기로 LRU cache를 초기화
• int get(int key) : 키가 있을 경우 키의 값을 반환하고, 없을 경우에는 -1 리턴
• void put(int key, int value) : 키가 있을 경우 키의 값을 업데이트하고, 없을 경우에는 값을 넣는데 이때 용량을 초과하면 가장 최근에 적게 사용한 키를 삭제하고 삽입

---

💡 아이디어

HashMap이랑 LinkedList를 사용해서 구현했다.

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은(최근에 가장 적게 사용된) 데이터를 제거하는 캐시 전략이다.

get()하거나 put() 했을 때 가장 최근에 사용한 것으로 간주하여 순서를 앞으로 갱신하면 되며, 캐시가 가득 찼을 때 새로운 데이터를 넣으면 가장 오래 안 쓰인 데이터를 제거한다.

remove(Node node)

	public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

위에서 노드 A를 삭제하려면 A의 앞 뒤 노드(head, B)의 연결을 끊으면 된다.

A의 앞 노드 head의 next = A의 다음 노드 B
A의 뒷 노드 B의 prev = A의 이전 노드 head

insertFront(Node node)

	public void insertFront(Node node) {
        // head -> A -> tail인 경우
        // node.next에 head.next = A 넣기
        // head.next.prev = A를 node로 변경

        node.next = head.next;
        head.next.prev = node;

        // head.next = node로 변경
        // head -> node -> A가 됨
        head.next = node;
        node.prev = head;
    }

위에서 맨 앞에 노드 B를 추가하려면

B의 next = head의 다음 노드 A
head의 뒷 노드인 A의 prev = B
head의 뒷 노드인 A = B
B의 prev = head

---

풀이

import java.util.*;

class LRUCache {
    class Node {
        int key, value;
        Node prev, next;

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

    Map<Integer, Node> map;
    int capacity;
    Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);

		// head와 tail 연결
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) return -1;

        // get하는 값 맨 앞으로 꺼내기
        Node node = map.get(key);
        remove(node);
        insertFront(node);

        return node.value;
    }
    
    public void put(int key, int value) {
        // key가 이미 있으면 update (삭제 후 앞에 넣기)
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            node.value = value;
            insertFront(node);
        } else {
            // 이미 꽉 차 있을 경우 최근에 가장 적게 사용한 Node 삭제
            if (map.size() == capacity) {
                Node lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }

            // 새 노드 넣기
            Node newNode = new Node(key, value);
            insertFront(newNode);
            map.put(key, newNode);
        }
    }

    public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void insertFront(Node node) {
        // head -> A -> tail인 경우
        // node.next에 head.next = A 넣기
        // head.next.prev = A를 node로 변경

        node.next = head.next;
        head.next.prev = node;

        // head.next = node로 변경
        // head -> node -> A가 됨
        head.next = node;
        node.prev = head;
    }
}