[LeetCode-자바] N_146 LRU Cache

0woy·2024년 5월 21일
0

코딩테스트

목록 보기
19/40

📜 문제

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);
    }
}

풀이의 핵심은 LinkedHashMap의 생성자이다.

- capacity: map의 초기 용량

- load factor(0.75f): 내부 해시 테이블의 크기 조정을 결정하는 비율 (default)

- access-order(true): 접근 순서 기억 여부
true인 경우, 맵의 요소에 접근할 때마다 맨 뒤로 이동 -> 가장 최근 요소가 맨 뒤에 위치

- removeEldestEntry재정의 하여 map의 크기가 capacity를 초과하는 경우, 가장 오래된 요소를 삭제한다.


✨ 결과

key-value 쌍을 저장하니 HashMap을 사용하는 건 알았다.
그런데 가장 오래된 요소를 제일 먼저 제거하는 자료구조도 존재할 것 같아서
찾아보니 LinkedHashMap을 알게 됐고, 풀 수 있었다!!


📖 참고

Yuri Lee - [JAVA] LinkedHashMap을 사용하는 방법
YaaaPyoung - LinkedHashMap으로 LRU 구현하기

0개의 댓글