Leetcode 146. LRU Cached

문제 링크 : https://leetcode.com/problems/lru-cache/

Map 자료형을 Cache Memory로 구현하였다. 자세한 것은 코드를 보면서 설명하도록 하겠다.

코드

// leetcode 146. LRUCache

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

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    // map에 key가 있다면 
    if (this.map.has(key)){
        // 우선순위 설정을 위해 삭제 후 다시 설정
        const val = this.map.get(key);
        this.map.delete(key);
        this.map.set(key,val);
        return val;
    // 없다면 return -1
    } else {
        return -1;
    }
    
    
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.get(key) === -1){
        if (this.map.size === this.capacity){
            for (let [firstKey] of this.map){
                this.map.delete(firstKey);
                break;
            }
        }
    }
    this.map.set(key, value);
};

세부적인 코드 설명

1. 생성자를 통해 cache 메모리의 총 크기와 cache 메모리를 담을 Map자료형을 생성한다.

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

2. get() : 각 메모리들의 우선순위를 기억하기 위해 해당 값이 있을 경우 해당 키 값을 삭제 후 다시 설정한다.

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    // map에 key가 있다면 
    if (this.map.has(key)){
        // 우선순위 설정을 위해 삭제 후 다시 설정
        const val = this.map.get(key);
        this.map.delete(key);
        this.map.set(key,val);
        return val;
    // 없다면 return -1
    } else {
        return -1;
    }
    
    
};

3. put() : cache메모리의 용량이 가득 찼을 경우 해당 메모리 우선순위 중 가장 오래된 우선순위를 제거한다.

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.get(key) === -1){
        if (this.map.size === this.capacity){
          	// map에 들어잇는 자료형 중 가장 왼쪽에 들어있는 값을 제거
            for (let [firstKey] of this.map){
                this.map.delete(firstKey);
                break;
            }
        }
    }
    this.map.set(key, value);
};

몰랐던 사실

• 내가 제일 처음 문제를 풀었을 때 시간초과가 발생하였다. 그 이유는 put함수에서 this.map의 가장 왼쪽에 있는 값을 빼내기 위해 다음과 같은 코드를 사용하였다.

const delKey = [...this.map.keys()][0];

다음과 같은 코드를 작성할 경우 spread 문법을 작성할 경우 새로운 객체를 생성하기 때문에 거기에서 오는 시간적 비용이 존재하여 시간 초과가 발생한 것이다.

새로 공부해야할 내용들

• 사실 문제는 해결을 했지만 시간복잡도와 메모리 사용량이 엄청나게 형편없었다. 그래서 그 이유를 알아보았더니 double link list를 사용하여 시간복잡도와 메모리 사용량을 엄청나게 줄일 수 있었던 것이었다. 그래서 다음 번에는 double link list를 사용하여 문제를 한 번 풀어보도록 하려고 한다.

• spread 문법이 익숙하지 않아 spread 문법에 대해 좀 더 깊이 있는 공부가 필요해 보인다.