[Leetcode] 146. LRU Cache

문제 바로가기

Linked List + Hash Map

linked list로 각 key-value 쌍의 사용 순서 구조를 유지하고, 각 node의 탐색을 위해 hash map을 사용한다.

각 get, put 작업에 대해
Time Complexity: $O(1)$
Space Complexity: $O(c)$ - $c$ : capacity

class Node:
    def __init__(self, key: int = -1, val: int = -1):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.dic = dict()
        self.lru = Node()
        self.mru = Node()
        self.lru.next = self.mru
        self.mru.prev = self.lru

    def get(self, key: int) -> int:
        if key in self.dic:
            cur = self.dic[key]
            self.updateAccessHistory(cur)
            return cur.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            # key exists
            cur = self.dic[key]
            self.updateAccessHistory(cur)
            cur.val = value
            return

        if len(self.dic) == self.cap:
            # delete LRU node
            target = self.lru.next
            del self.dic[target.key]
            self.lru.next = target.next
            target.next.prev = self.lru
            target.prev, target.next = None, None
            
        self.dic[key] = Node(key, value)
        self.updateAccessHistory(self.dic[key], True)
        
    def updateAccessHistory(self, node: Node, isNew: bool = False):
        if node == self.mru.prev:
            return
        
        if not isNew:
            # rearrange arround node's original position
            parent, child = node.prev, node.next
            parent.next = child
            child.prev = parent
        # rearrange arround the new position
        prevMru = self.mru.prev
        prevMru.next = node
        node.prev, node.next = prevMru, self.mru
        self.mru.prev = node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

collections.OrderedDict

삽입 순서가 유지되는 dictionary 자료형이다. move_to_end() 메서드를 사용하면 해당 키-값 쌍을 가장 마지막 순서로 미룰 수 있다. popitem() 메서드는 list의 pop()와 유사하다. 인자로 True를 받으면 FILO, False를 받으면 FIFO로 동작한다.

class LRUCache:
    from collections import OrderedDict
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()
        
    def get(self, key: int) -> int:
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1
        
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        else:
            if len(self.cache) == self.cap:
                self.cache.popitem(False)
        self.cache[key] = value