[LeetCode] 146. LRU Cache

😎풀이

해당 문제는 Node class를 선언하여 풀이해야 하는 문제이다.

처음엔 그저 Map을 사용해서 풀이하려 했으나, 간과한 점은 조회 및 업데이트 시점에 가장 최근 캐시로 유지되는 LRU에 대한 개념이 부족했음

해서 연결형 Node를 생성하여 가장 오래 조회되지 않은 노드를 식별하는 방법을 채택해 풀이하였다.

class Node {
    key: number;
    value: number;
    prev: Node | null;
    next: Node | null;

    constructor(key: number, value: number) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    private capacity: number;
    private cache: Map<number, Node>;
    private head: Node;
    private tail: Node;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.cache = new Map<number, Node>();
        
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    private removeNode(node: Node): void {
        const prev = node.prev!;
        const next = node.next!;
        prev.next = next;
        next.prev = prev;
    }

    private addNode(node: Node): void {
        // 항상 head 다음에 새 노드 추가
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next!.prev = node;
        this.head.next = node;
    }

    get(key: number): number {
        const node = this.cache.get(key);
        if (!node) return -1;

        // 접근한 노드를 가장 최근 위치로 이동
        this.removeNode(node);
        this.addNode(node);

        return node.value;
    }

    put(key: number, value: number): void {
        const existingNode = this.cache.get(key);
        
        if (existingNode) {
            // 기존 키가 있는 경우 값을 업데이트하고 위치 이동
            this.removeNode(existingNode);
            existingNode.value = value;
            this.addNode(existingNode);
        } else {
            // 새로운 키인 경우
            if (this.cache.size >= this.capacity) {
                // 캐시가 가득 찼으면 가장 오래된 항목(tail 이전 노드) 제거
                const lru = this.tail.prev!;
                this.removeNode(lru);
                this.cache.delete(lru.key);
            }
            
            const newNode = new Node(key, value);
            this.cache.set(key, newNode);
            this.addNode(newNode);
        }
    }
}