Leetcode[day23] - LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 우선, 기능을 나눠서 생각했다.

 - get(), put()을 O(1)의 시간복잡도를 갖기 위해서는 HashMap을 사용해야할 것 같았다.

 - 그런데, Map은 들어온 인덱스의 순서가 보장되지 않는다.

 - LinkedList는 들어온 인덱스는 보장 되지만, get()과 put()을 Element 값으로 돌려주려면, 시간이 걸린다.

 - Map과 LinkedList를 같이 쓰면 해결할 수 있지 않을까, 라고 생각했다.

 - 2시간 동안 풀다가 모르길래, 역시 유튜브를 봤다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 해당 문제를 풀기 위한 개념이 부족했다.

 - Map의 크기를 어떻게 유지해야할까?

 - Map이 특정 크기 이상이면, 처음 들어온 인덱스를 어떻게 제거할 수 있을까?

 

3. 다른 사람이 한 알고리즘 학습하기

 

https://www.youtube.com/watch?v=NsvGIgDo2Mk

 

4. 다른 사람의 알고리즘을 보고 학습한 내용

 

 

5. 다른 사람이 작성한 알고리즘을 보고, 알고리즘 작성해보기

 

class LRUCache {
    private HashMap<Integer, Node> cache;
    private Node head;
    private Node tail;
    private int capacity = -1;
    class Node{
        Node prev;
        Node next;
        int key;
        int value;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    
    private void append(Node node){
        node.next = tail.next;
        node.prev = tail;
        tail.next.prev = node;
        tail.next = node;
    }
    
    private void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    public LRUCache(int capacity) {
        cache = new HashMap();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.prev = tail;
        tail.next = head;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(cache.containsKey(key)){
            Node node = cache.get(key);
            remove(node);
            append(node);
            return cache.get(key).value;
        }
        
        return -1;
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            Node node = cache.get(key);
            if(node.value != value){
                node.value = value;
            }
            remove(node);
            append(node);
        }else{
            Node node = new Node(key, value);
            append(node);
            cache.put(key, node);
            if(cache.size() > capacity){
                Node first = head.prev;
                cache.remove(first.key);
                remove(first);
            }
        }    
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

 

6. 결과

 

 

7. 반성할 점

 

- 잘 하고 있는걸까

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3309/

Account Login - LeetCode