LRU 캐시 구현

문제 설명

LRU(Least Recently Used) 캐시를 구현하세요.

동작 방식

• 용량(capacity)이 정해진 캐시
• get(key): 키가 있으면 값 반환, 없으면 -1
• put(key, value): 키-값 저장, 용량 초과시 가장 오래된 항목 제거
• get, put 모두 O(1) 시간 복잡도

힌트

해시맵 + 이중 연결 리스트 조합 사용

예제

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)       // 1 반환
cache.put(3, 3)    // 2 제거됨 (가장 오래된)
cache.get(2)       // -1 반환