[Leetcode] 146. LRU Cache - JS

https://leetcode.com/problems/lru-cache/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
양수의 capacity으로 LRU cache를 초기화
get(key)는 key가 존재하면 key의 값을 반환한다. 없으면 -1 반환
put(key, value)는 key가 존재하는 경우 value를 업데이트하고 없으면 key-value 쌍을 추가하라.
key 갯수가 capacity를 초과하는 경우,
최근에 사용된 key를 제거하라.

제한조건
--------------------
- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- get, put은 시간복잡도 O(1)로 구현하라
- get, put은 최대 2 * 10^5 회의 호출이 일어난다.

 

2. 접근 방법

접근방법
--------------------
Map 자료구조는 삽입된 순서를 기억한다.

key-value 쌍으로 Map 자료구조에 순서대로 삽입된다.

이를 활용하여, get, put 호출 시 Map에 다시 설정하여 순서를 최신값으로 갱신할 수 있다.

또한, Map.prototype.keys()를 사용하면 Map의 key를 순서대로 반환하는 iterator를 참조할 수 있다.

iterator는 변수에 할당한 뒤, next() 메서드로 호출 시 key를 순서대로 하나씩 반환한다.

 

 

3. 코드

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

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.cache.has(key)) return -1;

    // key 지웠다가 제 설정하는 이유는 순서를 반영하기 위함
    const v = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, v);
    return this.cache.get(key)
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      // keys().next().value returns first item's key
      this.cache.delete(this.cache.keys().next().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)
 */

 

 

4. 복잡도 분석

- 시간복잡도: O(1)

- 공간복잡도: O(n)

 

Map 자료구조는 객체와 달리 key-value가 삽입된 순서를 기억하고 있고, keys() 메서드를 통해 iterator를 반환한다는 점을 연결리스트 처럼 활용하여 문제를 해결할 수 있다는 점을 다른 사람의 풀이를 통해 배웠다.