💬 문제
LRUCache 클래스를 구현
LRUCache(int capacity) capacity만큼의 용량을 가진 LRUCache 생성
int get(int key) key에 대응되는 value 값 반환
void put(int key, int value) key - value 형태의 데이터를 LRUCache에 삽입
put 함수 호출 시 용량이 꽉 찼다면 가장 오랫동안 사용되지 않았던 데이터 삭제
get, put은 시간 복잡도가 O(1)이어야 함
✍️ 나의 풀이
function Node(key, val) {
this.key = key;
this.val = val;
this.next = null;
this.prev = null;
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.map = new Map();
this.capacity = capacity;
this.head = new Node(null, null);
this.tail = new Node(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
};
LRUCache.prototype.insert = function(node) {
let last = this.tail.prev;
last.next = node;
node.prev = last;
node.next = this.tail;
this.tail.prev = node;
}
LRUCache.prototype.remove = function(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (this.map.has(key)) {
let useNode = this.map.get(key);
this.remove(useNode);
this.insert(useNode);
return useNode.val;
}
return -1;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.map.has(key))
this.remove(this.map.get(key));
let newNode = new Node(key, value);
this.insert(newNode);
this.map.set(key, newNode);
if (this.map.size > this.capacity) {
this.map.delete(this.head.next.key);
this.remove(this.head.next);
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/양방향 연결리스트를 활용하여 풀기 위해 Node 클래스 생성
초기화에서는 get 탐색을 위해 key-node로 저장할 map과,
연결리스트의 양 끝인 head와 tail 노드 생성
get과 put을 구현할 때 사용될 insert와 remove 함수 생성
get은 key에 해당하는 value를 반환함과 동시에 사용되었음을 기록하기 위해
해당 노드를 가장 끝 위치로 옮겨줘야 함
put은 이미 존재하는 key 값이면 value 수정 후 뒤로 옮겨주고,
없다면 가장 뒤에 새로 노드를 추가함
이 때 데이터 총 크기가 (map의 크기) 용량을 추가한다면
연결 리스트 가장 앞의 노드를 삭제
📌 결과
Accepted
Runtime 479ms (Beats 62.95%)
Memory 103.91MB (Beats 86.29%)
📚 러닝 포인트
사실 단순히 map만을 사용해서도 풀 수 있었다. 순서가 필요하다는 걸 알고 연결 리스트로 바꾸었지만, 나중에 확인해보니 key를 뽑아서 next로 이동하면서 확인할 수 있더라. 하지만 연결 리스트 관련 문제이기도 하고, 해당 방법을 사용하면 O(1)으로 구현할 수 없다. 물론 지금의 알고리즘도 map 함수를 사용할 때 무조건 O(1)이라고 확정할 수는 없지만, 그나마 나은 방법이라고 생각했다. 일단 구현을 쭉 했는데, 데이터 사용 시 리스트 순서가 변경되는 과정을 잘못 이해해서 단방향으로 구현해 버렸다. 여러번의 실패를 겪고 나서야 양방향으로 바꿔야된다는 것을 깨달았지만 그래도 깊고 깊은 에러와 그걸 처리하려는 if문의 향연이 이어졌다... 끝까지 혼자의 힘으로 구현해보고 싶었지만 시간이 너무 길어지고 이건 아닌 것 같다는 생각에 솔루션을 조금 참고해보았더니 insert와 remove 함수를 사용해서 get, put 함수를 구현하고 있었다. 다시 생각해보니 정말 두 과정이 insert, remove로만 동작할 수 있었다. 우와! 그래서 바로 해당 방법으로 처음부터 구현을 시작했다. 첫번째 노드를 이동시켜야하는 경우를 생각해서 빈 노드를 생성하여 head로 명시하고, tail은 그냥 마지막 노드를 가리키면서 변경시키려고 했는데 이 또한 마지막 노드를 변경할 때 여러가지 예외사항이 필요했다. 그래서 빈 tail 노드도 만들어서 명시시켜주었더니 훨씬 깔끔하게 구현할 수 있었다. 다음 문제가 연결 리스트의 마지막 문제에 hard 난이도인데, 꼭 혼자서 해낼 수 있기를 바란다...!
