[LC] 146. LRU Cache

[seungriyou]

https://leetcode.com/problems/lru-cache/

😭😭😭...

Approach

ref: https://www.romaglushko.com/blog/design-lru-cache/

[!caution] constraint: The functions get and put must each run in O(1) average time complexity.

1. O(1)에 원소 찾기 (for cache) ➡️ hash table

   • 하지만 least recently used 원소를 찾으려면 timestamp 등을 함께 사용해야 하는데, 그 과정에서 O(n) complexity가 발생한다.

2. O(1)에 least recently used 원소 찾기 (for LRU) ➡️ linked list

   • linked list에 원소를 자유롭게 add & remove 하기 위해 doubly-linked list로 구현한다.
   • 어떤 원소를 사용(get() or put()) 할 때마다 해당 원소를 linked list의 tail로 이동/추가하면, linked list의 head에는 least recently used 원소가 위치하게 된다.
   • 하지만 현재 사용하려는 원소를 linked list에서 찾는 과정에서 O(n) complexity가 발생한다.

3. 두 가지의 장점을 모두 사용하자! ➡️ hash table + linked list

   • 원소의 usage를 doubly-linked list로 관리하되, 현재 사용하려는 원소를 linked list에서 O(1)에 찾기 위해 hash table을 앞단에서 사용한다.

     ⬇️ 다음의 그림은 linked list의 방향이 거꾸로임 (least recently used 원소가 tail에 위치)

     

[!tip] linked list를 구현하기 위해 Node 클래스를 만들어도 되지만, 어떤 원소에 대해 next / prev를 저장하는 dict 만 관리해도 된다!

Complexity

• Time: get() & put(): O(1)
• Space: O(n)