[JAVA] 백준 1021 : 회전하는 큐

Queue에 이어서 Deque를 사용해야하는 문제이다
Deque는 큐의 반대 방향으로도 작동하는 알고리즘

index => 원하는 node의 value를 찾아 큐의 몇번째에 있는지 탐색
탐색한 위치 직전까지 (push(pop) <- 이 행동을 회전이라 칭한다) 회전을 하고 회전한 횟수만큼 카운트
그리고 index의 node를 pop을 해준다

import java.io.*;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        NodeManager<Integer> nodeManager = new NodeManager<>();

        st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int searchCnt = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= size; i++) {
            nodeManager.pushFront(new QueueNode<>(i));
        }

        st = new StringTokenizer(br.readLine());
        int[] searchValue = new int[searchCnt];
        for (int i = 0; i < searchCnt; i++) {
            searchValue[i] = Integer.parseInt(st.nextToken());
        }

        int rotateCnt = 0;
        for (int value : searchValue) {
            int index = nodeManager.indexOf(value);
            if (index <= nodeManager.getSize() / 2) {
                // 정방향 회전
                for (int i = 0; i < index; i++) {
                    nodeManager.pushFront(nodeManager.popFront());
                    rotateCnt++;
                }
            } else {
                // 역방향 회전
                for (int i = 0; i < nodeManager.getSize() - index; i++) {
                    nodeManager.pushBack(nodeManager.popBack());
                    rotateCnt++;
                }
            }
            nodeManager.popFront();
        }

        bw.write(String.valueOf(rotateCnt));

        bw.flush();
        bw.close();
        br.close();
    }
}

class QueueNode<T> {
    private final T value;
    private QueueNode<T> nextNode;
    private QueueNode<T> prevNode;

    public QueueNode(T value) {
        this.value = value;
        nextNode = null;
    }

    public T getValue() {
        return value;
    }

    public void setNextNode(QueueNode<T> nextNode) {
        this.nextNode = nextNode;
    }

    public QueueNode<T> getNextNode() {
        return nextNode;
    }

    public void setPrevNode(QueueNode<T> prevNode) {
        this.prevNode = prevNode;
    }

    public QueueNode<T> getPrevNode() {
        return prevNode;
    }
}

class NodeManager<T> {
    QueueNode<T> front, back;
    int size;

    public NodeManager() {
        front = back = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public QueueNode<T> popFront() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        QueueNode<T> node = front;
        if (front == back) {
            front = back = null;
        } else {
            front = front.getNextNode();
            front.setPrevNode(null);
        }
        size--;
        return node;
    }

    public void pushFront(QueueNode<T> node) {
        if (isEmpty()) {
            front = back = node;
        } else {
            back.setNextNode(node);
            node.setPrevNode(back);
            back = node;
        }
        size++;
    }

    public QueueNode<T> popBack() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        QueueNode<T> node = back;
        if (front == back) {
            front = back = null;
        } else {
            back = back.getPrevNode();
            back.setNextNode(null);
        }
        size--;
        return node;
    }

    public void pushBack(QueueNode<T> node) {
        if (isEmpty()) {
            front = back = node;
        } else {
            front.setPrevNode(node);
            node.setNextNode(front);
            front = node;
        }
        size++;
    }

    public T peekFront() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.getValue();
    }

    public T peekBack() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        return back.getValue();
    }

    public int indexOf(T value) {
        QueueNode<T> current = front;
        int index = 0;
        while (current != null) {
            if (current.getValue().equals(value)) {
                return index;
            }
            current = current.getNextNode();
            index++;
        }
        return -1; // 값을 찾지 못한 경우
    }
}