LinkedList : LRU Cache ( Doubly Linked List with Two Dummy Nodes 구현 )

https://leetcode.com/problems/lru-cache/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

이번엔 Doubly Linked List를 쓰되 dummy node를 front와 rear 각각에 둬서 두 개의 더미노드로 구현해봤다.

class Node:
    def __init__(self, val=None, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.front = Node()
        self.rear = Node()
        self.front.next = self.rear
        self.rear.prev = self.front
        self.cache = {}
        self.nodemap = {}

    def _add_node(self, newnode):
        last = self.rear.prev
        last.next = newnode
        self.rear.prev = newnode
        newnode.prev = last
        newnode.next = self.rear
        self.nodemap[newnode.val] = newnode

    def _pop_node(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p
        self.nodemap.pop(node.val)

    def get(self, key: int) -> int:
        if key in self.cache:
            self._pop_node(self.nodemap[key])
            self._add_node(Node(key))
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        #키가 이미 있는 경우와 없는 경우
        #용량이 다 찬 경우와 안찬경우

        """
            1. 키가 이미 있고 용량이 찼다. -> 기존 키 삭제하고 새 키 추가
            2. 키가 이미 있고 용량이 안찼다. -> 기존 키 삭제하고 새 키 추가
            3. 키가 없고 용량이 찼다. -> lru 키를 삭제하고 새 키를 추가
            4. 키가 없고 용량이 안찼다. -> 새 키를 추가
        """

        if key in self.cache:
            self._pop_node(self.nodemap[key])
        elif self.capacity == len(self.cache):
            self.cache.pop(self.front.next.val)
            self._pop_node(self.front.next)

        self._add_node(Node(key))

        self.cache[key] = value

 

14분 30초만에 풀었다.

푸는 시간이 비약적으로 줄었다 코드도 훨씬 간결하고 쉬워지고..

 

오늘 얻은 결론

1. 더미노드 최고

2. 주석으로 경우의 수 적어가면서 각각 어떻게 처리해야될지 써보고 공통된 부분 묶어서 코딩하니까 코드가 훨씬 간결해짐