Leetcode 146. LRU Cache

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

LRU Cache - LeetCode

 

문제

Least Recentry Used (LRU) cache(https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU)의 데이터 구조를 만들고자 한다.

 

LRUCache 클래스를 다음의 동작에 맞게 구현하라

• LRUCache(int capacity)는 정수 파라미터 capacity의 크기만큼의 LRU cache를 초기화한다.
• int get(int key) key에 해당하는 값을 반환한다. 키가 존재하지 않으면 -1 반환한다.
• void put(int key, int value) key가 존재한다면 key에 해당하는 value값을 반환한다. 그렇지 않다면 key와 value를 cache에 저장한다. 만약 capacity의 허용치를 초과한다면,  LRU 알고리즘에 따라 처리한다

get 메소드와 set 메소드는 O(1)의 수준으로 동작해야 한다.

 

코드

class LRUCache:

    def __init__(self, capacity: int):

        self.keyCache = list()

        self.capa = capacity

        self.value = {}

    def get(self, key: int) -> int:

        if key in self.keyCache:

            # put the key at first

            self.keyCache.remove(key)

            self.keyCache.insert(0, key)

            return self.value[key]

        return -1

    def put(self, key: int, value: int) -> None:

        if key not in self.keyCache:

            # when not enought location

            if len(self.keyCache) >= self.capa:

                self.value.pop(self.keyCache.pop())

            self.value[key] = value

        else:

            self.keyCache.remove(key)

            self.value[key] = value

        self.keyCache.insert(0, key)

---

문제의 마지막 조건을 보지 못해 단순 list로만 구현했다. 그래도 통과는 되었고 만족한다. 아마도 deque를 이용한다면 O(1)을 구현할 수 있지 않을까 생각한다.