코딩테스트 문제 (15) - 캐시

카카오 2018 블라인드 코딩테스트 기출문제입니다.

문제

1. cacheSize = 3, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
=> 50
2. cacheSize = 3, cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]
=> 21
3. cacheSize = 2, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]
=> 60
4. cacheSize = 5, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]
=> 52
5. cacheSize = 2, cities = ["Jeju", "Pangyo", "NewYork", "newyork"]
=> 16
6. cacheSize = 0, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
=> 25

 

풀이

캐쉬의 Least Recently Used 알고리즘을 구현하는 문제입니다. 6번 케이스처럼 캐시 사이즈가 0일 경우 모두 캐시 미스가 발생하여 5*5=25 의 실행시간이 소요됩니다.

LRU는 캐시 교체 전략 중 하나로 가장 오래 전 사용된 아이템을 버리는 알고리즘입니다. collections의 deque는 생성 시 mexlen 파라미터를 통해 크기를 지정할 수 있으며, 최대 크기를 넘어갈 시 가장 오래된 항목 (배열의 첫 번째 요소)를 제거합니다. 당연하게도 가장 최근에 사용된 아이템은 배열의 맨 마지막 요소라 생각할 수 있겠죠.

kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 난이도: 하