<Demopeu/>

[LeetCode] 146 LRU Cache JavaScript

[LeetCode] 146 LRU Cache JavaScript

problem-solvingLeetCodePrototypeLRU CacheMapIterator

📌 문제 설명

LRU Cache 문제 보기

📌 문제 접근

JS에서의 문제 접근

원래라면 해쉬를 사용한 후 양방향 연결 리스트를 활용해야하는 문제다. 하지만, js에서는 Map이라는 훌륭한 자료구조가 있다. 특징으로는 순서를 보장하고, 찾고 삭제하는데 O(1)의 시간복잡도를 가진다.

순서대로 삭제하기

Map은 순서를 보장하기 때문에, 가장 오래된 key를 삭제하기 위해 keys() 메서드를 사용하여 첫 번째 key를 가져올 수 있다. 하지만, 이걸 Array로 변환하면 시간복잡도가 O(n)이 되므로, Map을 쓰는 의미가 없어진다.

이때, Map은 이터러블한 객체다. 따라서 for...of 문을 사용하여 첫 번째 key를 가져올 수 있지만, 좀 더 js스럽게 하기 위해 keys() 메서드를 사용한다. keys() 메서드의 반환값은 이터레이터(iterator)이기 때문에, next() 메서드를 사용할 수 있다.

이때 next() 메서드의 반환값은 { value: key, done: boolean } 형태이다. 따라서 value 프로퍼티를 사용하여 첫 번째 key를 가져올 수 있다.

여담

현대 js은 syntax sugar가 잘 되어 있기 때문에, 굳이 prototype을 사용하지 않아도 된다. class가 더 직관적이고 코드리뷰할 때 이해하기 쉽지만, 간만에 직접 prototype을 사용하고 싶었다. js는 prototype 기반 언어라서, prototype을 잘 이해하는 것이 좋다고 생각한다.

📌 내가 작성한 코드

/**
 * @param {number} capacity
 */
const LRUCache = function(capacity) {
    this.map = new Map();
    this.capacity = capacity;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key,value);
    return value;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    this.map.delete(key);
    this.map.set(key,value);
    if (this.map.size > this.capacity){
        const oldKey = this.map.keys().next().value;
        this.map.delete(oldKey);
    }
};

/** 
 * 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)
 */

📌 시간 복잡도

O(1) - Map의 has/get/delete/set 연산과 가장 오래된 key 조회가 평균적으로 상수 시간에 처리됩니다.

📌 참고 링크