[알고리즘] 산타의 선물 공장 2

https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory-2/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static final int MAX_SIZE = 100_001;
    static Node[] head = new Node[MAX_SIZE];
    static Node[] tail = new Node[MAX_SIZE];
    static int[] size = new int[MAX_SIZE];
    static Node[] nodes = new Node[MAX_SIZE];
    static BufferedReader br;
    static StringTokenizer st;

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        int q = Integer.parseInt(br.readLine());
        for (int i = 1; i <= q; i++) {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            switch (cmd) {
                case 100:
                    int n = Integer.parseInt(st.nextToken());
                    int m = Integer.parseInt(st.nextToken());
                    init(n, m);
                    break;
                case 200:
                    int m_src = Integer.parseInt(st.nextToken());
                    int m_dst = Integer.parseInt(st.nextToken());
                    sb.append(moveAll(m_src, m_dst)).append("\n");
                    break;
                case 300:
                    m_src = Integer.parseInt(st.nextToken());
                    m_dst = Integer.parseInt(st.nextToken());
                    sb.append(replace(m_src, m_dst)).append("\n");
                    break;
                case 400:
                    m_src = Integer.parseInt(st.nextToken());
                    m_dst = Integer.parseInt(st.nextToken());
                    sb.append(divide(m_src, m_dst)).append("\n");
                    break;
                case 500:
                    int p_num = Integer.parseInt(st.nextToken());
                    sb.append(getGiftInfo(p_num)).append("\n");
                    break;
                case 600:
                    int b_num = Integer.parseInt(st.nextToken());
                    sb.append(getBeltInfo(b_num)).append("\n");
                    break;
            }
        }
        System.out.println(sb);
//        init(3, 5);
//        addLast(1, 1);
//        addLast(1, 2);
//        addLast(1, 3);
//        addLast(2, 4);
//        addLast(2, 5);
//        print(1);
//        print(2);
//        moveAll(1, 2);
//        print(2);
//        moveAll(3, 2);
//        print(2);
//        pollFirst(2);
//        print(2);
//        pollFirst(1);
//        print(1);
//        divide(2, 1);
//        print(2);
//        print(1);
//        replace(1, 2);
//        print(2);
//        print(1);
//        moveAll(1, 2);
//        replace(1, 2);
//        print(2);
//        print(1);
//        System.out.println(getGiftInfo(2));
    }

    private static void init(int n, int m) {
        for (int i = 1; i <= n; i++) {
            head[i] = new Node();
            tail[i] = new Node();
            head[i].next = tail[i];
            tail[i].prev = head[i];
        }

        for (int i = 1; i <= m; i++) {
            int beltId = Integer.parseInt(st.nextToken());
            Node node = addLast(beltId, i);
            nodes[i] = node;
        }
    }

    private static void print(int beltId) {
        Node h = head[beltId];
        while (h.next != tail[beltId]) {
            h = h.next;
            System.out.print(h.id + " ");
        }
        System.out.println();
    }
    private static Node addFirst(int beltId, Node node) {

        node.next = head[beltId].next;
        node.next.prev = node;
        head[beltId].next = node;
        node.prev = head[beltId];

        size[beltId]++;
        return node;
    }

    private static Node addLast(int beltId, int id) {
        Node node = new Node();
        node.id = id;

        node.prev = tail[beltId].prev;
        node.prev.next = node;
        tail[beltId].prev = node;
        node.next = tail[beltId];

        size[beltId]++;
        return node;
    }

    private static Node pollFirst(int beltId) {

        if (head[beltId].next == tail[beltId]) {
            return null;
        } else {
            Node temp = head[beltId].next;
            temp.next.prev = head[beltId];
            head[beltId].next = temp.next;

            temp.next = null;
            temp.prev = null;
            size[beltId]--;
            return temp;
        }
    }

    private static int moveAll(int m_src, int m_dst) {

        Node srcHead = head[m_src];
        Node dstHead = head[m_dst];

        Node srcTail = tail[m_src];
        Node dstTail = tail[m_dst];

        if (srcHead.next != srcTail) {
            srcTail.prev.next = dstHead.next;
            dstHead.next.prev = srcTail.prev;

            srcHead.next.prev = dstHead;
            dstHead.next = srcHead.next;

            srcHead.next = srcTail;
            srcTail.prev = srcHead;
        }

        size[m_dst] += size[m_src];
        size[m_src] = 0;

        return size[m_dst];
    }

    private static int replace(int m_src, int m_dst) {

        Node srcHead = head[m_src];
        Node dstHead = head[m_dst];

        Node srcTail = tail[m_src];
        Node dstTail = tail[m_dst];

        if (srcHead.next == srcTail && dstHead.next == dstTail) {
            return 0;
        } else if (srcHead.next == srcTail) {
            Node node = pollFirst(m_dst);
            addFirst(m_src, node);
        } else if (dstHead.next == dstTail) {
            Node node = pollFirst(m_src);
            addFirst(m_dst, node);
        } else {
            Node node1 = pollFirst(m_src);
            Node node2 = pollFirst(m_dst);

            addFirst(m_dst, node1);
            addFirst(m_src, node2);
        }
        return size[m_dst];
    }

    private static int divide(int m_src, int m_dst) {
        int l = size[m_src] / 2;
        Deque<Node> deque = new ArrayDeque<>();
        for (int i = 0; i < l; i++) {
            Node node = pollFirst(m_src);
            deque.addFirst(node);
        }
        for (int i = 0; i < l; i++) {
            addFirst(m_dst, deque.pollFirst());
        }
        return size[m_dst];
    }

    private static int getGiftInfo(int p_num) {
        Node node = nodes[p_num];
        Node prev = node.prev;
        Node next = node.next;
        int p = -1;
        int n = -1;
        if (prev.id != 0) {
            p = prev.id;
        }
        if (next.id != 0) {
            n = next.id;
        }

        return p + 2 * n;
    }

    private static int getBeltInfo(int b_num) {
        int h = head[b_num].next == tail[b_num] ? -1 : head[b_num].next.id;
        int t = head[b_num].next == tail[b_num] ? -1 : tail[b_num].prev.id;
        int s = size[b_num];
        return h + 2 * t + 3 * s;
    }

    static class Node {

        int id;
        Node prev;
        Node next;

        public Node(int id, Node prev, Node next) {
            this.id = id;
            this.prev = prev;
            this.next = next;
        }

        public Node() {
        }
    }
}

나의 풀이

- 링크드리스트를 구현해서 풀어야 하는 문제이다

- addLast, addFirst, pollFirst 등 최소한의 기능을 하는 걸 구현하고 조합하면 된다.

- size를 늘리고 줄이는 걸 addLast에서 해주었는데 바깥에서도 중복으로 해주어서 원하는 결과가 나오지 않았다.

- head와 tail 각각에 대해 더미 노드를 만들면 구현하기가 정말 편해진다!!!!!!!!!