Leetcode Java LFU Cache

문제

Link

코드

class LFUCache {

  private Node head;
  private Node tail;

  private Map<Integer, Node> map;
  private Map<Integer, Node> frequency;
  private int capacity;

  public LFUCache(int capacity) {
    this.head = new Node(-1, -1, -1);
    this.tail = new Node(-1, -1, -1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.map = new HashMap<>();
    this.frequency = new HashMap<>();
    this.capacity = capacity;
  }

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

  public void put(int key, int value) {
    if (this.capacity == 0) {
      return;
    } else if (this.map.containsKey(key)) {
      Node node = this.map.get(key);
      node.val = value;
      this.update(node);
    } else {
      Node node = new Node(key, value);
      if (this.map.size() == this.capacity) {
        Node temp = this.head.next;
        this.remove(temp);
        this.map.remove(temp.key);
      }
      this.map.put(key, node);
      this.insert(this.frequency.getOrDefault(1, this.head), node);
    }
  }

  private void update(Node node) {
    Node temp;
    if (this.frequency.containsKey(node.count + 1)) {
      temp = this.frequency.get(node.count + 1);
    } else {
      temp = this.frequency.get(node.count);
      if (temp == node) {
        temp = temp.prev;
      }
    }
    this.remove(node);
    node.count++;
    this.insert(temp, node);
  }

  private void remove(Node node) {
    if (node.prev.count != node.count && node.count != node.next.count) {
      this.frequency.remove(node.count);
    } else if (node == frequency.get(node.count)) {
      this.frequency.put(node.count, node.prev);
    }
    Node next = node.next;
    Node prev = node.prev;
    prev.next = next;
    next.prev = prev;
    node.next = null;
    node.prev = null;
  }

  private void insert(Node prev, Node curr) {
    Node next = prev.next;
    next.prev = curr;
    curr.next = next;
    curr.prev = prev;
    prev.next = curr;
    this.frequency.put(curr.count, curr);
  }

}

class Node {

  public Node prev;
  public Node next;

  public int val;
  public int key;
  public int count;

  public Node(int key, int val) {
    this.key = key;
    this.val = val;
    this.count = 1;
  }

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

}

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

결과

Link

설명

1. LFU(Least Frequently Used) 캐시의 데이터 구조를 설계하고 구현하는 문제이다.
   • 생성자인 LFUCache(int capacity)는 데이터를 담을 한계인 capacity를 이용하여 LFUCache 객체를 초기화한다.
   • 메서드인 get(int key)은 key에 해당하는 캐시를 반환한다. 존재하지 않는 경우 -1을 반환한다.
   • 메서드인 put(int key, int value)은 key에 해당하는 캐시가 존재하면 value로 수정하고, 존재하지 않는 경우 추가한다.
     • 캐시를 추가할 경우, 캐시의 수가 capacity에 도달하면 자주 사용하지 않은 캐시를 제거하고 추가한다.
     • 위의 경우 동일한 빈도를 가진 노드가 존재하면 자주 사용하지 않은 캐시를 제거한다.
2. 데이터 연결에 필요한 Node 클래스의 전역 변수를 정의한다.
   • prev는 이전 노드를 연결하기 위한 변수이다.
   • next는 다음 노드를 연결하기 위한 변수이다.
   • val은 캐시에 해당하는 값을 저장하기 위한 변수이다.
   • key는 캐시에 해당하는 키를 저장하기 위한 변수이다.
   • count는 해당 캐시가 발생한 횟수를 저장하기 위한 변수이다.
3. 데이터 연결에 필요한 Node 클래스의 생성자를 정의한다.
   • key와 val로 Node를 생성하는 경우, count를 1로 초기화한다.
   • key와 val, count로 Node를 생성하는 경우, 각 값을 객체에 넣어 초기화한다.
4. 문제 풀이에 필요한 변수를 정의한다.
   • head와 tail은 노드를 이어줄 경우, 가장 앞과 뒤의 캐시를 노드로 만들어 저장할 변수이다.
   • map은 key에 해당하는 캐시를 노드로 저장하기 위한 변수이다.
   • frequency는 노드의 발생 빈도 별 캐시를 노드로 저장하기 위한 변수이다.
5. 생성자인 LFUCache(int capacity)를 완성한다.
   • head와 tail를 key, value, count를 -1로 생성한 Node를 넣어준다.
   • head의 next에 tail을, tail의 prev에 head를 넣어 이어준다.
   • map과 frequency를 HashMap으로 초기화한다.
   • capacity에 주입된 capacity를 넣어준다.
6. 캐시의 변경을 위해 update(Node node) 메서드를 정의한다.
   • temp 노드를 아래 경우에 따라 넣어준다.
     • node의 $count + 1$ 번 발생한 노드가 frequency에 존재하는 경우, temp에 해당 노드를 넣어준다.
     • node의 $count + 1$ 번 발생한 노드가 frequency에 존재하지 않는 경우, temp에 node의 count번 발생한 노드를 frequency에서 찾아 넣어주고 temp와 node가 같으면 temp의 prev 노드를 temp에 넣어준다.
   • 7번에서 정의한 remove(Node node) 메서드를 이용하여 node를 제거해준다.
   • node의 count를 증가시키고, 8번에서 정의한 insert(Node prev, Node curr) 메서드를 temp와 node순으로 넣어 수행한다.
7. 캐시의 삭제를 위해 remove(Node node) 메서드를 정의한다.
   • node와 node의 prev와 next count가 모두 다른 경우, frequency에서 node의 count에 해당하는 노드를 삭제한다.
   • 위의 경우가 아니고 node가 frequency의 node의 count가 key인 노드와 동일한 경우, frequency 내 node의 count가 key인 값을 node의 prev 노드로 넣어 해당 노드를 끊어준다.
   • node의 next 노드와 prev 노드를 각각 정의하여 현재 node를 배제하여 연결시켜준다.
8. 캐시의 삽입을 위해 insert(Node prev, Node curr) 메서드를 정의한다.
   • prev 자리에 curr 노드를 넣어주고, prev와 curr을 이어준다.
   • frequency 내 curr의 count가 키인 노드에 curr을 넣어준다.
9. 메서드인 get(int key)을 완성한다.
   • map에 key가 키인 노드가 존재하는 경우, 아래를 수행한다.
     • map에서 key가 키인 노드를 가져와 해당 노드로 6번에서 정의한 update(Node node) 메서드를 수행하여 캐시 발생 빈도를 증가하여 갱신해준다.
     • 위에서 가져온 node의 val 값을 반환한다.
   • 위의 경우가 아니면 문제에서 요구한 -1을 반환한다.
10. 메서드인 put(int key, int value)을 완성한다.
    • capacity가 0인 경우 캐시 저장이 불가능하므로, 아무것도 수행하지 않는다.
    • map에 key가 키인 노드가 존재하는 경우, 아래를 수행한다.
      • map에서 key가 키인 노드를 가져와 val 값에 value를 넣어준다.
      • 위에서 가져온 노드로 6번에서 정의한 update(Node node) 메서드를 수행하여 캐시 발생 빈도와 값을 갱신해준다.
    • 그 외의 경우 아래를 수행한다.
      • node에 key와 value를 이용한 새 노드를 정의해 넣어준다.
      • map의 크기가 capacity와 동일한 경우, head의 next 노드를 7번에서 정의한 remove(Node node) 메서드로 삭제하고 map에서도 해당 key에 해당하는 캐시를 삭제한다.
      • map에 key에 해당 하는 키에 node를 넣어준다.
      • 8번에서 정의한 insert(Node prev, Node curr) 메서드를 이용하여 frequency에 1번 발생한 캐시의 노드가 있으면 해당 노드를, 없으면 head를 prev자리에 node를 curr 자리에 넣어 수행하여 새 캐시를 이어준다.

소스

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