090. LRU 캐시

[문제] LRU 캐시(Least Recently Used cache)를 제공하는 MCP 서버를 구현한다. 캐시는 키-값을 보관하는 임시 저장소인데, 자리가 정해져 있어 꽉 차면 무언가를 버려야 한다. LRU는 "가장 오래 안 쓴 것부터 버린다"는 규칙이다. 여기서 "쓴다"는 것은 값을 저장(put)하거나 조회(get)하는 것을 말한다. 이 캐시의 정원은 3이며, 정원을 넘기면 가장 오래 사용되지 않은 키를 내보낸다(evict). [구현할 함수] - put(key: str, value: str) -> int key에 value를 저장한다. 이 키를 "가장 최근 사용"으로 표시한다. 정원(3)을 넘기면 가장 오래 사용되지 않은 키를 하나 내보낸다. 저장 후 현재 캐시 크기를 반환한다. - get(key: str) -> str key의 값을 반환한다. 없으면 빈 문자열 ""을 반환한다. 조회에 성공하면 그 키를 "가장 최근 사용"으로 표시한다. - get_cache_state() -> array<string> 현재 캐시의 키 목록을 반환한다. 가장 최근 사용된 키가 맨 앞에 온다. 비어 있으면 빈 배열 []을 반환한다. [입력·상태] 서버는 최대 3개의 키-값을 유지하며, 각 키가 마지막으로 사용된 순서를 기억한다. 초기에는 비어 있다. [제약] - 정원(capacity)은 3으로 고정된다. - 키와 값은 문자열이다. - get_cache_state는 최근 사용 순(최근 → 오래된 순)으로 키를 나열한다. [예시] (각 예시는 초기 빈 상태에서 시작) put("a", "apple") -> 1 get("a") -> "apple" get("없음") -> "" put("a","A"); put("b","B"); put("c","C") get_cache_state() -> ["c", "b", "a"] # 가장 최근에 넣은 c가 맨 앞 put("a","A"); put("b","B"); put("c","C"); put("d","D") get_cache_state() -> ["d", "c", "b"] # 정원 초과로 가장 오래된 a가 빠짐 get_cache_state() -> [] # 빈 상태