[알고리즘] Leetcode > #146. LRUCache

문제링크

Leetcode #146. LRUCache

풀이방법

LRU Cache 안드로이드 개발 중 종종 들은 키워드이다. LRU 알고리즘은 페이징 교체 알고리즘 중 하나인데, 가장 최근에 쓰이지 않은 페이지를 교체하는 알고리즘이다. 이 알고리즘을 적용한 캐시가 LRU 캐시이다!

페이징 교체 알고리즘을 공부한 적 있어서 알고리즘은 아는데 어떤 자료구조를 사용해 구현하면 좋을지 고민해봤다.

일단, 삽입삭제가 빨라야하고 그 순서를 저장해야 했다.

• 배열: 공간효율도 좋지 않고 삭제 시 모든 element의 최근 사용시점을 확인해야해서 O(N)의 시간복잡도를 갖는다
• 우선순위큐: 삽입삭제 시 힙을 재구성 해 O(logN)의 시간복잡도를 갖는다
• 트리맵: 트리로 맵이 구현되어 있고 정렬된 상태의 자료구조인데, 우선순위큐와 같이 삽입삭제 시 O(logN)의 시간복잡도를 갖는다
• LinkedHashMap: 삽입삭제 O(1), hit 시 재구성에도 O(1)의 시간복잡도를 갖는다.

LinkedHashMap을 상속받아 구현했다!

코드

class LRUCache extends LinkedHashMap<Integer, Integer> {
    
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true); // access-ordered
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1); // get 연산시 알아서 순서를 바꿔 재배치
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    } // 내부적으로 호출되는 함수로, true return 시 가장 오래된 element를 삭제한다
}

+) 이 자료구조에서 위 풀이방법과 같이 access-ordered로 사용하면 get 연산시에도 재배치가 일어난다. 따라서 멀티스레드 환경에서 사용할 경우 이를 고려해 thread-safe하게 해야한다!