LRU Cache

1. 맨 처음에는 시간초과가 나왔어오...😥
처음에 계획했을 때에는 객체에는 순서가 없어서, 이를 기억해주도록 객체로만 접근해도 시간 복잡도가 뚫리지 않을까?! 싶었어요. 그래봤자 시간 복잡도가 제 눈에는 최대 (put 메서드 호출 수) * O(n)인 거 같았거든요.
그럼에도 뚫리지 않자, 원인을 분석했을 때, 아무래도 객체를 따로 또 순서를 기억해야 하는 점과, 또 forEach로 순회하는 부분에서 걸린다는 느낌이 강하게 들었습니다!

/**
 * @param {number} capacity
 */
 const LRUCache = function(capacity) {
    this.size = capacity;
    this.seqNumber = 0;
    this.obj = {};
    this.objLength = 0;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    this.seqNumber += 1;
    if(this.obj[key] !== undefined) this.obj[key].lastUsedSeqNumber = this.seqNumber;
    return this.obj[key] === undefined ? -1 : this.obj[key].value;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    this.seqNumber += 1;
    if (this.obj[key] === undefined && this.size === this.objLength) {
        const keys = Object.keys(this.obj);
        let lRUkey = undefined;
        let lRUSeqNumber = Infinity;
        keys.forEach(key => {
            let lastUsedSeqNumber = this.obj[key].lastUsedSeqNumber
            if (lastUsedSeqNumber < lRUSeqNumber) {
                lRUkey = key;
                lRUSeqNumber = lastUsedSeqNumber;
            }
        })
        delete this.obj[lRUkey];
    }
    if (this.obj[key] === undefined) {
        if (this.objLength !== this.size) this.objLength += 1;
    }
    this.obj[key] = { value, lastUsedSeqNumber: this.seqNumber };
};

1. 그래서 해결 방법은 일단 객체의 순서를 기억하자 → Map() 객체를 쓰자!
그리고 forEach의 경우도 결국에는 Map 객체로 접근하면 순회할 필요가 없어서(정확히 말하자면, 각 객체의 프로퍼티에 기록된 마지막 접근했던 seqNumber을 찾을 이유가 없어서),
결과적으로 이를 해결할 수 있었네요!

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

/*
    1. 먼저 세팅할 때 size를 만들어주고, 가장 최근의 사용된 걸 알려면 순서를 알아야 하므로 이러한 기능이 있는 Map 객체를 쓴다.
    2. 가져올 때는 map에서 있으면 갖고 오고, 없으면 -1을 리턴.
       이때 중요한 건, 순서를 다시 재배치 시켜야 하므로 삭제시켰다가 다시 세팅해준다.
    3. put의 경우  
*/

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    const value = this.recentlyUsedOrder.get(key);
    if (value === undefined) return -1;

    this.recentlyUsedOrder.delete(key);
    this.recentlyUsedOrder.set(key, value);
    return value;
};

/*
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
/*
    put 조건이 일단 사이즈가 꽉차면 하나 빼주고
    다시 하나 집어넣어준다.
    1. 하나 빼주는 뭔가가 있어야 돼! -> 반환하는 리턴값
    2. 다시 집어넣어주는 뭔가가 있어야 돼! -> 반환하는 리턴값
*/
LRUCache.prototype.put = function(key, value) {
    //하나 빼주는 뭔가가 있어야 돼!
    if (this.recentlyUsedOrder.get(key) === undefined && this.recentlyUsedOrder.size === this.size) {
        const iter = this.recentlyUsedOrder[Symbol.iterator]();
        const next = iter.next();
        this.recentlyUsedOrder.delete(next.value[0]);
    }
    this.recentlyUsedOrder.delete(key);
    this.recentlyUsedOrder.set(key, value);
};

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

const 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