LeetCode - LRU Cache

문제 설명

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.

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Example :

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

Constrains

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

Solution

• 풀이가 accepted 되었지만 TC가 좋지 않다. 마지막 사용된 시간을 기록하기위한 freqMap 대신에
  linkedlist로 삭제순서를 관리하면 속도가 향상될 수 있을까?
• linkedlist 사용시,
  • 삭제없이 element put : O(n) 동일. hashmap에서 key로 put 하는것과 연결리스트 마지막에 추가해주는 속도는 비슷할것으로 예상됨
  • 삭제하고 element put : O(n) -> O(1) 속도 향상. Map에서 삭제 대상을 순환탐색하는 과정없이 삭제대상 연결리스트의 마지막 부분을 삭제하면 됨.
  • get의 경우 : O(1) -> O(n) 속도 저하. get으로 사용된경우, 해당 element를 삭제 대상 연결리스트의 제일 후순위로 보내주어야 하므로, 해당 element를 연결리스트에 찾는 비용 발생

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.time = 1;
    this.capacity = capacity;
    this.keyMap = new Map();
    this.freqMap = new Map();
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    let val = this.keyMap.get(key);
    if (val == null) {
        return -1
    } else {
        this.freqMap.set(key, this.time++);
        return val;
    }
    
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (!this.freqMap.has(key) && this.keyMap.size >= this.capacity) {   
        let leastFreqkey = 0;
        let leastFreqVal = 100000;
        for (let element of this.freqMap) {
            if (element[1] < leastFreqVal) // element[0] : key, element[1] : value
            {
                leastFreqkey = element[0];     
                leastFreqVal = element[1];
            }
        }
        // 가장 이전에 사용된것 삭제
        this.freqMap.delete(leastFreqkey);
        this.keyMap.delete(leastFreqkey);     
    }
     this.keyMap.set(key, value);
     this.freqMap.set(key, this.time++);
    return null
};

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

연결리스트 방식으로 보완 해야겠다!