LRU Cache

Gold해시맵연결 리스트설계

LRU(Least Recently Used) 캐시를 설계하세요. capacity 크기의 캐시로 get(key)과 put(key, value) 연산을 각각 O(1)에 수행해야 합니다. 캐시 용량이 초과되면 가장 오래 사용되지 않은 항목을 제거합니다.

AI 분석 결과

0우수

AI 분석 점수

AlgoSu AI가 생성한 실제 분석 샘플입니다.

OrderedDict를 활용한 Python 표준 라이브러리 기반 구현으로 간결하고 효율적입니다. 타입 힌트와 __slots__를 추가하면 코드 품질이 더욱 향상됩니다.

시간: O(1)공간: O(capacity)

카테고리별 점수

correctness90

get/put 연산이 LRU 정책을 정확히 구현합니다. 용량 초과 시 가장 오래된 항목을 올바르게 제거합니다.

efficiency95

OrderedDict의 move_to_end와 popitem이 O(1)이므로 get/put 모두 O(1) 시간복잡도를 달성합니다.

readability85

클래스 구조가 명확하지만 메서드에 docstring을 추가하면 가독성이 향상됩니다.

bestPractice80

OrderedDict[int, int] 타입 힌트를 명시하고 __slots__를 사용하면 메모리 효율이 개선됩니다.

제출 코드

1from collections import OrderedDict
2
3class LRUCache:
4    def __init__(self, capacity: int):
5        self.capacity = capacity
6        self.cache = OrderedDict()
7
8    def get(self, key: int) -> int:
9        if key not in self.cache:
10            return -1
11        self.cache.move_to_end(key)
12        return self.cache[key]
13
14    def put(self, key: int, value: int) -> None:
15        if key in self.cache:
16            self.cache.move_to_end(key)
17        self.cache[key] = value
18        if len(self.cache) > self.capacity:
19            self.cache.popitem(last=False)

개선된 코드 예시

1from collections import OrderedDict
2
3class LRUCache:
4    __slots__ = ('capacity', 'cache')
5
6    def __init__(self, capacity: int) -> None:
7        self.capacity = capacity
8        self.cache: OrderedDict[int, int] = OrderedDict()
9
10    def get(self, key: int) -> int:
11        """키 조회 — 존재하면 최신으로 갱신 후 반환."""
12        if key not in self.cache:
13            return -1
14        self.cache.move_to_end(key)
15        return self.cache[key]
16
17    def put(self, key: int, value: int) -> None:
18        """키-값 삽입 — 용량 초과 시 LRU 항목 제거."""
19        if key in self.cache:
20            self.cache.move_to_end(key)
21        self.cache[key] = value
22        if len(self.cache) > self.capacity:
23            self.cache.popitem(last=False)