146. LRU Cache

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 key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

My Answer 1: Output Limit Exceeded (17 / 20 test cases passed.)

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.used = []      # 사용 순서대로

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        self.used.remove(key)
        self.used.append(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        # update
        if key in self.cache:
            self.used.remove(key)
            self.used.append(key)
            self.cache[key] = value
        
        else:
            if len(self.cache) == self.capacity:
                leastkey = self.used[0]
                self.used.remove(leastkey)
                del self.cache[leastkey]
            self.used.append(key)
            self.cache[key] = value


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

init: cache 는 딕셔너리로, used 는 리스트로 만들고
딕셔너리는 크기 제한이 안되는 것 같으니까 capacity 변수를 따로 만들어서 put 함수에서 사용함

get: key 가 없으면 -1 리턴
있으면 used 의 key 를 맨 마지막으로 옮기고 cache[key] 리턴

put: key 가 이미 있으면 update => used 와 cache[key] 값 업데이트
없으면 cache 크기가 꽉 찼을 경우 leastkey 제거하고 key 를 put 해준다

리스트를 써서 그런가...? Output Limit Exceeded ㅠㅠ

Solution 1: Runtime: 164 ms - 96.40% / Memory Usage: 23.3 MB - 88.84%

class LRUCache:

    def __init__(self, capacity: int):
        self.dict = {}
        self.capacity = capacity   

    def get(self, key: int) -> int:
        if key not in self.dict:
            return -1
        val = self.dict.pop(key)  #Remove it first before inserting it at the end again
        self.dict[key] = val   
        return val        

    def put(self, key: int, value: int) -> None:
        if key in self.dict:    
            self.dict.pop(key)
        else:
            if len(self.dict) == self.capacity:
                del self.dict[next(iter(self.dict))]         
        self.dict[key] = value


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

이거 좀 천재같기두..
pop 을 이용해서 update 하고 get 한다 => 알아서 사용 순서가 바뀌는 격..

self.dict[next(iter(self.dict))] 는 iter 로 반복문 돌리고 next 로 하나하나 디버깅하듯이 함
제일 첫번째 값이 least 일 것이니까 next 를 한번만 해준다

"doubly linked list and dictionary" 라고.. listnode 쓰는 솔루션도 봤는데....
너무 끔찍해서 걍 이걸로 외우기로~