11 to 9, Day 24

Today, ToDoList

• 큐 자료구조

---

큐 자료구조

LRU 캐시 구현하기

package queue;

import java.util.Deque;
import java.util.LinkedList;

public class LRU {

    public int size;
    public Deque<Integer> cache;

    public LRU(int size) {
        this.size = size;
        this.cache = new LinkedList<>();
    }

    //LRU 캐시 구현하기
    //n개 중에서 가장 오래된 값을 삭제하고 number에 해당하는 입력 값을 캐시에 추가하기
    //시간복잡도 O(N), 공간복잡도 O(N)
    public void query1(int number) {
        if (cache.contains(number)) { //O(N)
            cache.remove(number); //O(N)
            cache.addFirst(number);
        } else {
            if (cache.size() == size) {
                cache.removeLast();
            }
            cache.addFirst(number);
        }
    }

    //LRU 캐시 구현하기
    //현재 캐시에 저장된 값을 출력하기
    public void print() {
        System.out.println(this.cache);
    }


    public static void main(String[] args) {
        LRU lru = new LRU(5);
        lru.query1(1);
        lru.query1(2);
        lru.query1(3);
        lru.query1(4);
        lru.query1(5);
        lru.query1(6);
        lru.query1(3);

        lru.print();
    }
}

package queue;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    public int size;
    public Map<Integer, Node<Integer>> map;

    public Node<Integer> head, tail;

    public LRUCache(int size) {
        this.size = size;
        this.map = new HashMap<>();
    }

    private class Node<E> {
        public Node(E value) {
            this.value = value;
        }

        E value;
        Node<E> next;
        Node<E> prev;
    }

    //LRU 캐시 구현하기
    //n개 중에서 가장 오래된 값을 삭제하고 number에 해당하는 입력 값을 캐시에 추가하기
    //커스텀 노드와 HashMap을 사용하여 시간 복잡도 줄이기.
    //시간복잡도 O(1), 공간복잡도 O(N)
    public void query(int number) {
        Node<Integer> node;
        if (map.containsKey(number)) { //O(1)
            node = map.get(number);
            removeNode(node); //O(1)
        } else {
            if (map.size() == size) {
                removeNode(map.remove(this.tail.value)); //O(1)
            }
            node = new Node<>(number);
            map.put(number, node); //O(1)
        }
        addTohead(node); //O(1)
    }

    public void removeNode(Node<Integer> node) {
        if ( node.prev == null ) {
            this.head = node.next;
            this.head.prev = null;
        } else if ( node.next == null ) {
            this.tail = node.prev;
            this.tail.next = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    public void addTohead(Node<Integer> node) {
        if ( this.head == null ) {
            this.tail = node;
        } else {
            this.head.prev = node;
            node.next = this.head;
        }
        this.head = node;
        this.head.prev = null;
    }

    public void print() {
        Node<Integer> node = head;
        while (node!=null) {
            System.out.println(node.value);
            node = node.next;
        }
    }


    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.query(1);
        lruCache.query(2);
        lruCache.query(3);
        lruCache.query(4);
        lruCache.query(5);
        lruCache.query(1);

        lruCache.print();
    }
}

package queue;

import java.util.LinkedHashSet;

public class NewLRUCache {

    public int size;
    public LinkedHashSet<Integer> set;

    public NewLRUCache(int size) {
        this.size = size;
        this.set = new LinkedHashSet<>();
    }

    //LRU 캐시 구현하기
    //n개 중에서 가장 오래된 값을 삭제하고 number에 해당하는 입력 값을 캐시에 추가하기
    //자바에서 제공하는 LinkedHashSet을 사용하여 HashSet과 달리 순서를 보장할 수 있다.
    //LinkedHashSet은 LRU 캐시에 매우 최적화된 자료구조이다.
    //시간복잡도 O(1), 공간복잡도 O(N)
    public void query(int number) {
        if ( set.contains(number) ) { //O(1)
            set.remove(number); //O(1)
            set.add(number); //O(1)
        } else {
            if ( set.size() == size ) {
                set.remove(set.iterator().next()); //O(1)
            }
            set.add(number); //O(1)
        }
    }

    //LRU 순서의 반대로 출력된다.
    //필요시 LRU 순서로 출력하려면 reverse 구현해야함.
    public void print() {
        System.out.println(set);
    }


    public static void main(String[] args) {
        NewLRUCache lruCache = new NewLRUCache(5);
        lruCache.query(1);
        lruCache.query(2);
        lruCache.query(3);
        lruCache.query(4);
        lruCache.query(5);
        lruCache.query(1);

        lruCache.print();
    }
}

바이너리 트리 BFS 순회

package queue;

import java.util.ArrayDeque;
import java.util.Queue;

public class BinaryTree {

    Node root;

    private static class Node {
        Node left;
        Node right;
        int value;

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

    //바이너리 트리의 층 합계 중 최대값 구하기 - Queue
    //
    //시간복잡도 O(N), 공간복잡도 O(B),B=트리의 최대 넓이
    public int maxSumOfTree(Node root) {
        if ( root == null ) {
            return 0;
        }

        int max = root.value;
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);

        while ( !queue.isEmpty() ) {
            int size = queue.size();
            int sum = 0;
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                sum += node.value;
                if ( node.left != null ) {
                    queue.offer(node.left);
                }
                if ( node.right != null ) {
                    queue.offer(node.right);
                }
            }
            max = Math.max(max, sum);
        }

        return max;
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        //Node node7 = new Node(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        //node3.right = node7;

        System.out.println(binaryTree.maxSumOfTree(node1)==15);
    }
}