1. Time Limit Exceeded
일단 초반에 타임 초과과 났다.
기본적인 발상은 그냥 단순하게 HashMap을 사용한다. 하지만 해시맵은 순서를 보장하지 모하기 때문에,
deque 의 key 값 관리를 통해, 순서를 보장하게 해주려고 하였다. 하지만..
시간 초과 났다. 조금 더 연구해 보니, deque 의 remove는 처음부터 탐색하여 매칭되며 지워주는 메소드라 시간 복잡도가 O(n)이다. 그래서 다른 알고리즘을 채택하여야 했다.
class LRUCache {
/*
LRU(Least Recent Used) 캐시의 제약 조건을 따르는 데이터 구조를 설계합니다.
LRUCache 클래스를 구현합니다.
LRUCache(int 용량) 양수 크기 용량으로 LRU 캐시를 초기화합니다.
int get(int key) 키가 존재하면 해당 키의 값을 반환하고, 그렇지 않으면 -1을 반환합니다.
void put(int key, int value) 키가 존재하는 경우 키 값을 업데이트합니다. 그렇지 않으면 키-값 쌍을 캐시에 추가합니다. 키 수가 이 작업의 용량을 초과하는 경우 가장 최근에 사용된 키를 제거합니다.
get 및 put 함수는 각각 O(1) 평균 시간 복잡도로 실행되어야 합니다.
*/
HashMap <Integer, Integer> hashMap = null;
Deque <Integer> dq= null;
int capacity = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
dq = new LinkedList<>();
hashMap = new HashMap<>(capacity);
}
public int get(int key) {
if(hashMap.containsKey(key)) {
dq.remove(key);
dq.addLast(key);
return hashMap.get(key);
} else {
return -1;
}
}
public void put(int key, int value) {
if(hashMap.containsKey(key)) {
dq.remove(key);
dq.addLast(key);
hashMap.remove(key);
hashMap.put(key, value);
}
else {
if(hashMap.size() == capacity) {
hashMap.remove(dq.pollFirst());
dq.addLast(key);
hashMap.put(key, value);
}
else {
hashMap.put(key, value);
dq.addLast(key);
}
}
}
2. HashMap, Doubly Linked List
class LRUCache {
Node head;
Node tail;
int capacity;
HashMap <Integer, Node> hashMap;
public class Node {
public Node(int key, int value) {
this.key = key;
this.value = value;
}
int value;
int key;
Node previous;
Node next;
}
public LRUCache(int capacity) {
this.capacity = capacity;
head = null;
tail = null;
hashMap = new HashMap<>();
}
public int get(int key) {
if(hashMap.containsKey(key)) {
Node cur = hashMap.get(key);
if(cur != tail) {
if(cur == head) {
head = head.next;
}
if(cur.previous != null) {
cur.previous.next = cur.next;
}
if(cur.next != null) {
cur.next.previous = cur.previous;
}
cur.previous = tail;
tail.next = cur;
cur.next = null;
tail = cur;
}
return cur.value;
}
else {
return -1;
}
}
public void put(int key, int value) {
if(get(key) == -1) {
Node node = new Node(key, value);
if(tail == null) {
head = node;
tail = node;
}
else {
node.previous = tail;
tail.next = node;
tail = node;
}
hashMap.put(key, node);
if(hashMap.size() > capacity) {
hashMap.remove(head.key);
head.next.previous = null;
head = head.next;
}
}
else {
hashMap.get(key).value = value;
}
}
}
/**
* 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);
*/
모든 복잡도 O(1)
3. ArrayDeque
class LRUCache {
/*
LRU(Least Recent Used) 캐시의 제약 조건을 따르는 데이터 구조를 설계합니다.
LRUCache 클래스를 구현합니다.
LRUCache(int 용량) 양수 크기 용량으로 LRU 캐시를 초기화합니다.
int get(int key) 키가 존재하면 해당 키의 값을 반환하고, 그렇지 않으면 -1을 반환합니다.
void put(int key, int value) 키가 존재하는 경우 키 값을 업데이트합니다. 그렇지 않으면 키-값 쌍을 캐시에 추가합니다. 키 수가 이 작업의 용량을 초과하는 경우 가장 최근에 사용된 키를 제거합니다.
get 및 put 함수는 각각 O(1) 평균 시간 복잡도로 실행되어야 합니다.
*/
HashMap <Integer, Integer> hashMap = null;
Deque <Integer> dq= null;
int capacity = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
dq = new ArrayDeque<>();
hashMap = new HashMap<>(capacity);
}
public int get(int key) {
if(hashMap.containsKey(key)) {
dq.remove(key);
dq.addLast(key);
return hashMap.get(key);
} else {
return -1;
}
}
public void put(int key, int value) {
if(hashMap.containsKey(key)) {
dq.remove(key);
dq.addLast(key);
hashMap.remove(key);
hashMap.put(key, value);
}
else {
if(hashMap.size() == capacity) {
hashMap.remove(dq.pollFirst());
dq.addLast(key);
hashMap.put(key, value);
}
else {
hashMap.put(key, value);
dq.addLast(key);
}
}
}
}
스터디 공부할때, Deque 구현체를 ArrayDeque 로 구현하면 더 빠르고, 거의 O(1) 의 시간복잡도가 나온다고 들어서,
얼른 바꿔서 다시 채점했는데 맞았다.. 신기했다.
근데 arrayDeque 랑 LinkedList remove 함수는 둘다 O(n) 인데 .. 왜 맞은거지 ..;
정리
- **LinkedList에서 remove(key)는 O(n)**이 맞지만, ArrayDeque에서는 remove(key)가 O(n)으로 동작하는 것이 일반적이다.
- 그러나 LeetCode에서의 특정 최적화나 테스트 케이스에 따라 **ArrayDeque의 remove(key)가 O(1)**처럼 평가되었을 가능성이 있다.
- LeetCode 채점 시스템에서 특정 케이스에 대해 ArrayDeque가 잘 동작하면서 맞았다고 평가됐을 수 있다.
그래서 결국 문제의 핵심은 ArrayDeque가 실제로 잘 최적화된 테스트 케이스에서 맞았다는 거야.
그렇다네 GPT가 ..