https://leetcode.com/problems/lru-cache/
코드설명
Class(레퍼런스 객체) + 해시맵(HashMap) + LinkedHashMap 을 활용합니다.
LRU Cache는 Least Recently Used Cache를 제거하는 캐싱 정책입니다.
이를 구현할때, 기본적으로 HashMap을 사용해야한다는 점은 O(1) 안에 처리하라는 조건이 있어 알 수 있습니다.
HashMap을 사용하면서, LRU Cache를 구현하기 위해서는 Cache가 사용된 데이터들의 사용빈도를 기반으로 하여 관리하면서, 그 위치를 알아야 하기에 ArrayList를 사용해야 한다고 생각했습니다. 하지만, 이 방식은 순서는 보장하지만, 시간복잡도 O(1)안에 처리하지 못합니다. ( 그안에서 삭제될경우 안의 요소들이 이동되기 때문 )
그렇기에 HashMap<Integer, Node> 를 통해서 처리해야만 시간복잡도 O(1) 안에 처리할 수 있습니다.
이러한 구현을 LinkedHashMap에서 구현하여 자바 라이브러리 API 로 제공하는데, 해당 방식을 사용하여도 됩니다.
특이사항은, LinkedHashMap 객체를 인스턴스화할때, capacity = 용량, 0.75f는 해시테이블이 얼마나 차면 리사이징할지, true는 accessOrder, 즉 들어온 순서대로 처리할지에 대하여 입니다. 이 코드 자체가 LRU를 보장합니다.
LinkedHashMap은 Key가 들어온 순서대로 저장하는데, 이때 true로 설정함으로써 접근순서에 따른 순서로 바꾸어줍니다.
추가로, 제거할시에는 removeEldestEntry 를 Override하여 구현함으로써 초과될시 자동으로 가장 오래전에 사용된 객체를 삭제해줍니다.
this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity; // 용량 초과 시 가장 오래된 항목 제거
}
};
}코드
Node 래퍼런스 클래스를 활용하여 cache HashMap에서 가리키는 위치를 포인터시킵니다.
아래 오답코드를 보면 알 수 있듯이, 가장 문제점은 위치를 갱신시키는 방법에 대한 것 이었습니다.
Node Class를 활용하고, Dummy Class인 Oldest와 Latest를 통해 위치를 갱신시키는 로직이 사라지고 주소값 기반으로 처리할 수 있게 됩니다. 처음에 드는 생각은, put 과정에서 기존의 Node를 그대로 사용하면 더 좋을 것 이라고 생각했지만, Cache의 Key값이 바뀔 수 있으므로 그 과정에서 새로 해당 cache값의 value값을 변경시켜주어야 합니다.
class LRUCache {
private int capacity;
private Map<Integer, Node> cache;
private Node oldest;
private Node latest;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.oldest
= new Node(-1, -1);
this.latest = new Node(-1, -1);
this.oldest.next = this.latest;
this.latest.prev = this.oldest;
}
public int get(int key) {
if(cache.containsKey(key)){
Node node = cache.get(key);
remove(node);
insert(node);
return node.val;
}
return -1;
}
private void remove(Node node){
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
}
private void insert(Node node){
Node prev = latest.prev;
Node next = latest;
prev.next = next.prev = node;
node.next = next;
node.prev = prev;
}
public void put(int key, int value) {
if(cache.containsKey(key)){
remove(cache.get(key));
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
insert(newNode);
if(cache.size() > capacity){
Node lru = oldest.next;
remove(lru);
cache.remove(lru.key);
}
}
}
class Node{
int key;
int val;
Node prev;
Node next;
public Node(int key, int val){
this.key = key;
this.val = val;
this.prev = prev;
this.next = null;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
위의 구현이 제공되는 LinkedHashMap 라이브러리입니다.
import java.util.*;
class LRUCache {
private final int capacity;
private final LinkedHashMap<Integer, Integer> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity; // 용량 초과 시 가장 오래된 항목 제거
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
처음에 시도한 오답코드입니다.
틀린 이유는, Cache가 꽉 찬 상태에서 새로운 <key, value>가 들어왔을 때 LRU Cache 정책에 의해 맨 앞의 값을 제거하거나 맨 뒤의 값을 제거해야하는데, 이렇게 유지하기 위해서는 다른 값들의 Index들이 PUT, GET 하는 과정에서 모두 이동시켜줘야 되면서 시간복잡도가 평균 O(1) 이 되도록 할 수 없기 때문입니다.
즉, 코드의 구조자체가 시간복잡도의 조건을 통과하지 못합니다.
class LRUCache {
HashMap<Integer, Integer> hashmap;
ArrayList<int[]> arr;
int capacity = 0;
public LRUCache(int capacity) {
hashmap = new HashMap<Integer, Integer>();
arr = new ArrayList<int[]>();
this.capacity = capacity;
}
//가장 최근에 사용된걸 맨뒤로 바꿔주자.
public int get(int key) {
int arrIdx = hashmap.get(key);
return arr.get(hashmap.get(key));
}
public void put(int key, int value) {
if(capacity <= 0){
//swap first and last
int[] lastArr = arr.get(arr.size() - 1);
int lastKey = lastArr[0];
int lastValue = lastArr[1];
int[] firstArr = arr.get(0);
int firstKey = fisrtArr[0];
int firstValue = firstArr[1];
hashmap.put(lastKey, 0);
arr.get(0) = lastArr;
hashmap.remove(firstKey);
capacity++;
}
hashmap.put(key, arr.size());
arr.add(new int[] {key, value});
capacity -= 1;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/