leetcode 146 python 파이썬 소스코드 + LRU 알고리즘

스크·2023년 11월 28일

코딩기록

목록 보기

4/6

문제링크

https://leetcode.com/problems/lru-cache/?envType=study-plan-v2&envId=top-interview-150

📢 문제 간략설명

LRU(Least Recent Used) 캐시 의 제약 조건을 따르는 데이터 구조를 설계합니다 .

LRUCache 클래스를 구현합니다 .

LRUCache(int capacity)양수 크기 로 LRU 캐시를 초기화합니다.
int get(int key) 키가 존재하면 key 의 값을 반환하고 , 그렇지 않으면 -1을 반환합니다.
void put(int key, int value) 존재하는 경우 key 값을 업데이트합니다.그렇지 않으면 key-value쌍을 캐시에 추가합니다.

키 수가 capacity이 작업에서 초과하는 경우 가장 최근에 사용한 키를 제거합니다 .

기능 get과 put각각은 평균 시간 복잡도로 실행되어야 합니다 O(1)

📢 즉,

LRU 알고리즘을 짜는 것
참고 : 링크텍스트

📌풀이 알고리즘

📌소스코드 및 풀이방법

class Node:
    def __init__(self, key = None, value = None, left = None, right = None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        
        self.head.right = self.tail
        self.tail.left = self.head
        


    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._removeNode(node)
            self._insertAfter(self.head, node)
            return node.value
        return -1


    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            self._removeNode(node)
            self._insertAfter(self.head, node)
            node.value = value
            return

        if len(self.cache) == self.capacity:
            remove = self.tail.left
            self._removeNode(remove)
            del self.cache[remove.key]

        node = Node(key, value)

        self._insertAfter(self.head, node)
        self.cache[key] = node

    def _removeNode(self, node):
        node.right.left = node.left
        node.left.right = node.right
    
    def _insertAfter(self, prev, node):
        node.left = prev
        node.right = prev.right
        
        prev.right.left = node
        prev.right = node