Leetcode Java LRU Cache

문제

Link

코드

class LRUCache {

  private Map<Integer, Node> map = new HashMap<>();

  private Node head = new Node(0, 0);
  private Node tail = new Node(0, 0);

  private int capacity;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  public int get(int key) {
    if (this.map.containsKey(key)) {
      Node node = this.map.get(key);
      this.remove(node);
      this.insert(node);
      return node.value;
    } else {
      return -1;
    }
  }

  public void put(int key, int value) {
    if (this.map.containsKey(key)) {
      this.remove(this.map.get(key));
    }
    if (this.map.size() == this.capacity) {
      this.remove(this.tail.prev);
    }
    this.insert(new Node(key, value));
  }

  private void remove(Node node) {
    this.map.remove(node.key);
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  private void insert(Node node) {
    this.map.put(node.key, node);
    Node next = this.head.next;
    this.head.next = node;
    node.prev = this.head;
    next.prev = node;
    node.next = next;
  }
    
}

public class Node {

    public Node prev;
    public Node next;
    public int key;
    public int value;

    public Node() {
    }

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }

}

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

결과

Link

설명

1. Least recently used(LRU)로 캐시를 저장하는 알고리즘을 구현하는 문제이다.
   • 생성자인 LRUCache(int capacity)는 캐시의 크기를 capacity로 입력받는다.
   • 메서드인 get(int key)은 캐시에 key가 존재하면 값을 반환하고, 존재하지 않으면 -1를 반환한다.
   • 메서드인 put(int key, int value)은 key 값이 존재하면 해당 value의 값을 주어진 value의 값으로 변경하고, 존재하지 않는 경우 key-value 쌍을 캐시에 저장한다.
     • 단, capacity의 크기를 초과하는 경우 가장 최근에 사용된 key-value 쌍을 제거한다.
2. 문제 풀이에 필요한 전역 변수를 정의한다.
   • 변수 map은 캐시를 저장 하는 변수이다.
   • 변수 head와 tail은 Node를 연결해서 사용하기 위하여 선언한 변수이다.
   • 변수 capacity는 생성자를 통해 주입받은 캐시의 크기를 저장하기 위한 변수이다.
3. 문제 풀이에 필요한 Node 클래스를 정의한다.
   • Node를 연결하기 위해 해당 node 이전의 Node를 저장할 변수 prev를 정의한다.
   • Node를 연결하기 위해 해당 node 이후의 Node를 저장할 변수 next를 정의한다.
   • Node의 key 값을 저장할 변수 key를 정의한다.
   • Node의 value 값을 저장할 변수 value를 정의한다.
   • Node를 생성하기 위한 기본 생성자를 정의한다.
   • Node를 생성할 때 key와 value를 입력받아 전역 변수에 넣어줄 생성자를 정의한다.
4. 주어진 생성자인 LRUCache(int capacity)를 완성한다.
   • 주입된 capacity를 전역변수 capacity에 저장한다.
   • head.next에 tail을 넣고, tail.prev에 head를 넣어 서로를 연결시켜준다.
5. 주어진 메서드인 get과 put을 활용 할 때 순서를 변경하고 캐시에서 해당 Node를 빼기 위한 remove 메서드를 정의한다.
   • 캐시인 map에서 주어진 Node인 node를 삭제한다.
   • node의 연결을 수정하기 위해 node.prev.next에 node.next를, node.next.prev에 node.prev를 넣어준다.
6. 주어진 메서드인 get과 put을 활용 할 때 순서를 변경하고 캐시에서 해당 Node를 추가하기 위한 remove 메서드를 정의한다.
   • 캐시인 map에 node.key값을 이용하여 node를 넣어준다.
   • node의 연결을 수정하기 위해 head.next를 지역 변수 next에 저장하고, node를 넣고 next와 node를 연결시켜준다.
7. 주어진 메서드인 get(int key)를 완성한다.
   • 캐시를 저장한 map에 key를 이용하여 Node가 존재하는지 검증하여 아래를 수행한다.
     • Node가 존재하는 경우, 지역 변수인 node에 저장한 후 캐시인 map에 remove 메서드와 insert 메서드를 통해 Node 순서를 갱신하고 node.value를 반환한다.
     • Node가 존재하지 않는 경우, -1을 반환한다.
8. 주어진 메서드인 put(int key, int value)를 완성한다.
   • 캐시를 저장한 map에 key를 이용하여 Node가 존재하면, 해당 Node를 remove 메서드로 제거해준다.
   • map의 크기가 capacity와 동일한 경우, 최근 사용한 변수인 tail.prev Node를 remove 메서드로 제거해준다.
   • 주어진 key와 value를 이용하여 새 Node를 생성하고 캐시인 map에 추가해준다.

소스

Sample Code는 여기에서 확인 가능합니다.