[PS] Leet | 146. LRU 캐시

문제

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

예시

Input

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

조건

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

답

JavaScript의 hash map을 사용하면 O(1) 시간으로 LRU를 찾을 수 있습니다.

 

Hash map의 key-value 쌍들이 실제로는 doubly linked-list로 구현되어 있어, key가 추가된 순서를 기억할 수 있기 때문입니다.

 

따라서 put( ) 또는 get( )이 실행될 때마다 해당 key를 map에 추가하면, key에 접근했던 순서가 기록되게 됩니다.

 

이미 접근한 적이 있던 key면 hash map에서 삭제 후 다시 추가하면 됩니다.

 

LRUCache( )

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.cache = new Map();
    this.size = capacity;
};

LRUCache.get( )

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

LRUCache.put( )

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        // re-link
        this.cache.delete(key);
    }
    else if (this.size === this.cache.size) {
        this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
};