백준 1021번 회전하는 큐

백준 1021번 회전하는 큐

문제
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

접근과정

• 뽑아내고자 하는 원소의 위치(인덱스)들이 순서대로 주어지지 않기 때문에 원형 큐의 자료구조대로 2번과정처럼 Front의 원소를 Rear로 보내거나 3번과정처럼 Rear원소를 Front로 보내는 과정을 거쳐서 뽑고자 하는 원소를 Front에 위치시켜야한다.
• 2번, 3번과정을 최소한으로 해야하기때문에 내가 뽑고자 하는 원소의 위치가 Front로 오게 하기위서는 2번을 해야할지 3번을 해야할지 선택해야하고, 그에대한 조건을 생각해야한다.
• 내가 뽑고자하는 원소의 값은 알필요가 없고 몇번째 원소를 뽑느냐가 중요하기 때문에 LinkedList에 1~N까지 숫자를 채워놓고 이 List에서 1,2,3번 과정을 수행한다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

// 백준 1021 큐 문제
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int nidx = in.nextInt();

        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            queue.add(i + 1);
        }

        ArrayList<Integer> idxList = new ArrayList<>();
        for (int i = 0; i < nidx; i++) {
            idxList.add(in.nextInt());
        }

        int count = 0;
        for (Integer num : idxList) {
            if (queue.peek() == num) {
                queue.poll();
                continue;
            } else {
            	//2번과정을 해야할지 3번과정을 해야할지에 대한 조건
                if (queue.indexOf(num) > (double) queue.size() / 2) {
                    while (queue.peek() != num) {
                        queue.addFirst(queue.pollLast());
                        count++;
                    }
                    queue.poll();
                } else {
                    while (queue.peek() != num) {
                        queue.addLast(queue.pollFirst());
                        count++;
                    }
                    queue.poll();
                }

            }
        }
        System.out.println(count);
    }
}