[Leetcode 146] - LRU Cache w/ Python

문제

 

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. 

 

Implement the LRUCache class: 

- LRUCache(int capacity): Initialize the LRU cache with positive size capacity. 

- int get(int key) : Return the value of the key if the key exists, otherwise return -1.

- void put(int key, int value) :  Update the value of the key if the key exists. Otherwise, add the keyvalue pair to the cache.

If the number of keys exceeds the capacity from this operation, evict the least recently used key.

 

The functions get and put must each run in O(1) average time complexity.

 

 

LRU Cache 클래스를 완성하자

- capacity: Capcity/용량을 초과하지 못하게 클래스를 설계

- get: 키가 있으면 값을 리턴, 없다면 -1

- put: 키가 있다면 값을 업데이트, 아니라면 추가. 용량을 초과한다면 최근에 가장 안쓴 키를 제거

 

 

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

 

---

 

예시

 

예시 1

 

 

---

 

 

풀이

 

 

1. 순서가 중요하기 때문에 키/값을 편하게 해주는 Dictionary 중에서 Ordered Dictionary 사용

2. 이를 통해 값이 들어가 있으면 move_to_end 사용해서 뒤로 옮기고

3. 가장 사용을 안한 키는 제일 왼쪽에 있기 때문에 popitem(0)을 사용해서 제거

 

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity 
        self.dict = OrderedDict() # 순서가 중요한 문제, OrderDict 필요
        
    def get(self, key: int) -> int:
        if key in self.dict: # 값을 찾았으면
            self.dict.move_to_end(key) # 제일 뒤로 옮긴다
            return self.dict[key]
        else:
            return -1 # 유저야 값이 없는데...?
        
    def put(self, key: int, value: int) -> None:
        if key in self.dict:
            self.dict.move_to_end(key) # 키를 찾으면 제일 뒤로 옮기고
        self.dict[key] = value # 값을 없데이트 하거나 추가
        if len(self.dict) >self.cap : # 하지만 용량이 초과되면?
            self.dict.popitem(0) # 제일 앞에꺼 바이바이

 

 

ㄴㅇㅅ