[Programmers] [1차] 캐시

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

문제 설명

LRU 알고리즘을 구현하는 문제이다. 구현 방법에는 여러가지가 있으며 그 중 Java에서 제공하는 LinkedHashMap을 이용하여 해결하였다. LinkedHashMap는 removeEldestEntry() 라는 메소드를 제공한다. 이 메소드는 put() 호출 시 내부에서 실행되는데 정렬 순서를 기준으로 가장 오래된 Entry를 제거한다. LinkedHashMap의 기본 정렬은 삽입 순서이다. 따라서 이를 접근 기준으로 변경해야 한다. 이를 생성자에서 제공한다.

LinkedHashMap<Integer, String> map
    = new LinkedHashMap<>(int initialCapacity, float loadFactor, boolean accessOrder);

첫 번째 파라미터는 초기 크기값, 두 번째 파라미터는 일정 이상의 요소 삽입 시 크기를 늘리기 위한 임계값, 마지막 파라미터가 정렬 순서를 설정하는 값이다. true일 경우 접근 기준으로 정렬하며 false일 경우 삽입 기준으로 정렬한다. 기본값은 삽입이므로 true로 설정해야 한다.

또한 removeEldestEntry()를 오버라이딩 해주어야 한다. 기본 처리가 false만 반환하게 하므로 이를 적용하려면 꼭 오버라이딩 해주어야 한다.

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(capacity, loadfactor, accessOrder) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

위처럼 오버라이딩하면 put() 호출 시 내부에서 removeEldestEntry()가 실행되고 현재 size()가 원하던 용량보다 커진 경우 accessOrder에 따라 가장 오래된 Entry가 제거된다. 이를 활용해 비교적 간단히 LRU 알고리즘을 구현할 수 있다.

코드

import java.util.Map;
import java.util.LinkedHashMap;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        LRUCache<String, Object> cache = new LRUCache<>(cacheSize);

        for (String city: cities) {
            cache.put(city.toLowerCase(), null);
        }
        
        return cache.getRuntime();
    }
    
    static class LRUCache<K, V> {
        private int capacity;
        private int runtime;
        private LinkedHashMap<K, V> cache;
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.runtime = 0;
            this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > capacity;
                }
            };
        }
        
        public int getRuntime() {
            return runtime;
        }
        
        public void put(K key, V value) {
            runtime += cache.containsKey(key) ? 1 : 5;
            cache.put(key, value);
        }
    }
}