Hashmap: 146. LRU Cache ★★★

146. LRU Cache

 

https://youtu.be/7ABFKPK2hD4?si=R9ZwBAdBVxHzBRga

 

# Node 추가 
class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {} # map key to node

        # left=LRU, right=most recent
        self.left, self.right = Node(0, 0), Node(0, 0)

        # set double linked list
        self.left.next, self.right.prev = self.right, self.left  

    # remove node from list
    def remove(self, node):
        prv, nxt = node.prev, node.next
        prv.next, nxt.prev = nxt, prv

    # insert node at left of right: 제일 오른쪽 노드의 바로 왼쪽에 삽입
    def insert(self, node):
        prv, nxt = self.right.prev, self.right
        prv.next = nxt.prev = node
        node.next, node.prev = nxt, prv

    def get(self, key: int) -> int:
        if key in self.cache:
            # to do: update most recent
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        if len(self.cache) > self.capacity:
            # remove from the list and delete the LRU from the hashmap
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]




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

# left: LRU head / right: most recent로 되게.
# double linked list 사용
# 해쉬맵도 사용

 

내가 푼 코드

class LRUCache:

    def __init__(self, capacity: int):
        # Initialize the cache with the given capacity
        # 주어진 용량(capacity)으로 캐시를 초기화
        self.capacity = capacity  # Maximum capacity of the cache
                                  # 캐시의 최대 용량
        self.hashmap = {}         # Dictionary to store key-value pairs
                                  # 키-값 쌍을 저장하는 딕셔너리
        self.use = []             # List to track the usage order of keys
                                  # 키의 사용 순서를 추적하는 리스트

    def get(self, key: int) -> int:
        # If the key exists in the cache
        # 키가 캐시에 존재하는 경우
        if key in self.hashmap:
            # Remove the key from its current position in the usage list
            # 사용 순서 리스트에서 해당 키를 제거
            self.use.remove(key)
            # Append the key to the end of the usage list to mark it as recently used
            # 해당 키를 사용 순서 리스트의 맨 뒤에 추가하여 최근 사용으로 표시
            self.use.append(key)
            # Return the value associated with the key
            # 키와 연결된 값을 반환
            return self.hashmap[key]
        else:
            # If the key does not exist, return -1
            # 키가 존재하지 않으면 -1 반환
            return -1        

    def put(self, key: int, value: int) -> None:
        # If the key already exists in the cache
        # 키가 이미 캐시에 존재하는 경우
        if key in self.hashmap:
            # Remove the key from its current position in the usage list
            # 사용 순서 리스트에서 해당 키를 제거
            self.use.remove(key)
            # Append the key to the end of the usage list to mark it as recently used
            # 해당 키를 사용 순서 리스트의 맨 뒤에 추가하여 최근 사용으로 표시
            self.use.append(key)
            # Update the value associated with the key
            # 키와 연결된 값을 업데이트
            self.hashmap[key] = value
        else:
            # If the cache is full (exceeds capacity)
            # 캐시가 가득 찬 경우 (용량 초과)
            if len(self.hashmap) >= self.capacity:
                # Remove the least recently used key (front of the list)
                # 가장 오래된 키를 제거 (리스트의 맨 앞)
                recent_key = self.use.pop(0)
                # Remove the corresponding key-value pair from the hashmap
                # hashmap에서 해당 키-값 쌍을 제거
                del self.hashmap[recent_key]

            # Add the new key-value pair to the cache
            # 새로운 키-값 쌍을 캐시에 추가
            self.use.append(key)  # Add the key to the usage list
                                  # 사용 순서 리스트에 키 추가
            self.hashmap[key] = value  # Store the key-value pair in the hashmap
                                       # hashmap에 키-값 쌍 저장

 

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        self.use = [] # 사용한 키 순서 저장

    def get(self, key: int) -> int:
        if key in self.hashmap:
            self.use.remove(key)
            self.use.append(key)
            return self.hashmap[key]
        else:
            return -1        

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            self.use.remove(key)
            self.use.append(key)
            self.hashmap[key] = value
        else:
            # 용량 넘치면
            if len(self.hashmap) >= self.capacity:
                recent_key = self.use.pop(0) # 리스트의 맨 앞 키 제거
                del self.hashmap[recent_key]

            # 새로운 쌍 추가
            self.use.append(key)
            self.hashmap[key] = value

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

 

최종 코드

class LRUCache:

    def __init__(self, capacity: int):
        # LRUCache 의 용량 capacity: 양수 싸이즈
        self.capacity = capacity
        self.hashmap = {}
        self.use = [] # 사용 히스토리 저장

    def get(self, key: int) -> int:
        # key 가 있으면 return key, 없으면 return -1
        if key in self.hashmap:
            # 해당 키를 사용 히스토리에서 제거하고,
            self.use.remove(key) 
            # 해당 키를 히스토리 최신으로 쌓음
            self.use.append(key)
            return self.hashmap[key]
        else:
            return -1        

    def put(self, key: int, value: int) -> None:
        # key 있으면 업데이트, 
        """
         If the number of keys exceeds the capacity from this operation, 
            evict the least recently used key.
                  the least 가장 적게 사용된 = 
        이 연산으로 인해 키의 개수가 용량(capacity)을 초과하면, 
            가장 오래전에 사용된 키를 제거(evict)하라
        """
        if key in self.hashmap:
            # 키가 있으면 업데이트
            self.hashmap[key] = value
            # 해당 키를 사용 히스토리에서 제거하고,
            self.use.remove(key) 
            # 해당 키를 히스토리 최신으로 쌓음
            self.use.append(key)
        else:
            # 키가 없으면 추가하는데
            # 만약 용량을 넘어서면,즉, 지금 full 이면
            if len(self.hashmap) >= self.capacity:
                # 가장 오래된 키 값 삭제하고, 새로 추가
                # old_key = self.use[0]
                # self.use.remove(old_key)
                old_key = self.use.pop(0) 
                del self.hashmap[old_key]
                # self.hashmap[key] = value
                # self.use.append(key)
            # else:
            #     # 용량이 아직 있으면 그냥 추가
            #     self.hashmap[key] = value
            #     self.use.append(key)
            self.hashmap[key] = value
            self.use.append(key)


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