LRU 캐시 재로딩 횟수 세기
자바스크립트 코딩테스트 문제로 lru-cache-simulation 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
사용자가 화면을 요청할 때마다 서비스는 작은 LRU 캐시에 최근 사용한 화면 데이터를 저장합니다.
캐시에 이미 있는 화면을 요청하면 재로딩하지 않지만, 그 화면은 가장 최근에 사용한 항목이 됩니다. 캐시에 없는 화면을 요청하면 재로딩 횟수가 1 증가하고 캐시에 추가됩니다.
캐시 크기가 capacity를 초과하면 가장 오래 사용하지 않은 화면을 하나 제거합니다. 전체 요청을 처리했을 때 필요한 재로딩 횟수를 반환하는 countCacheReloadsLru 함수를 작성하세요.
제한사항
0 <= capacity <= 1000000 <= requests.length <= 100000requests의 각 원소는 길이 1 이상 20 이하의 문자열입니다.- 같은 문자열은 같은 화면을 의미합니다.
- 캐시 용량이
0이면 어떤 화면도 저장할 수 없습니다. - 반환값은 전체 요청 중 캐시에 없어 새로 불러온 횟수입니다.
예시
- 입력:
capacity = 2,requests = ["A", "B", "A", "C", "B", "A"]-> 출력:5 - 입력:
capacity = 3,requests = ["A", "B", "C", "A", "D", "B", "E"]-> 출력:6 - 입력:
capacity = 0,requests = ["home", "search", "home"]-> 출력:3 - 입력:
capacity = 1,requests = ["X", "X", "X"]-> 출력:1
힌트
- JavaScript의
Map은 삽입 순서를 기억합니다. - 이미 있는 키를 최근 사용으로 옮기려면 지운 뒤 다시 넣는 방식을 사용할 수 있습니다.
- 캐시 크기가
capacity보다 커졌을 때map.keys().next().value가 가장 오래된 키입니다.
해설
LRU 캐시는 “가장 오래 사용하지 않은 항목”을 먼저 비우는 캐시입니다. 따라서 각 화면이 캐시에 있는지뿐 아니라, 최근 사용 순서도 함께 관리해야 합니다.
Map을 사용하면 키 존재 여부를 빠르게 확인하면서 삽입 순서도 유지할 수 있습니다. 요청한 화면이 이미 캐시에 있다면 캐시 적중이므로 재로딩 횟수는 늘리지 않습니다. 대신 최근 사용 항목으로 갱신하기 위해 해당 키를 삭제한 뒤 다시 넣습니다.
요청한 화면이 캐시에 없다면 재로딩 횟수를 1 늘리고 캐시에 넣습니다. 그 결과 캐시 크기가 capacity보다 커졌다면, Map의 가장 앞에 있는 키를 제거합니다. 이 키가 현재 가장 오래 사용하지 않은 항목입니다.
캐시 용량이 0인 경우에는 어떤 항목도 저장할 수 없으므로 모든 요청이 재로딩입니다. 이 경우 requests.length를 바로 반환할 수 있습니다.
각 요청마다 Map 연산을 상수 시간에 처리하므로 전체 시간 복잡도는 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.