[LeetCode-자바] N_146 LRU Cache

0woy·2024년 5월 21일

Java LinkedHashMap leetcode

코딩테스트

목록 보기

19/42

📜 문제

LRU cache를 클래스를 작성하는 문제이다.

LRUCache(int capacity): capacity(>0) 크기만큼 초기화
int get(int key): key가 존재하는 경우 value 값을 반환, 그렇지 않으면 -1 반환
void put(int key, int value): key의 value값을 추가하거나 갱신
cache가 꽉 찬 경우, 가장 오랫동안 사용되지 않은 key 삭제 후 추가.
get, put 메서드는 O(1) 시간 복잡도로 수행 돼야 한다.

O(1)의 시간 복잡도를 가져야 하므로 HashMap을 사용해야 한다.
하지만, HashMap은 삽입 순서를 보장하지 않기 때문에 삽입 순서를 보장하는 LinkedHashMap을 사용한다.

❓ LRU (Least Recently Used)

페이지 교체 시 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법.
EX) A B C D E D F

WIKIPEDIA - Cache replacement policies

🍳 전체 소스 코드

class LRUCache {
    Map<Integer, Integer> map;
    int max;
    public LRUCache(int capacity) {
        map = new LinkedHashMap<>(capacity,0.75f,true){
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size()>capacity;
            }
        };
    }

    public int get(int key) {
      return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key,value);
    }
}