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
을 사용한다.
페이지 교체 시 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법.
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 구현하기