[백준/JAVA] 1021번 회전하는 큐

• 덱을 활용하여 큐를 회전시키는 문제
  https://www.acmicpc.net/problem/1021

1. 문제

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

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

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

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

2. 문제 접근

1) 첫째 줄에서 큐의 크기 N과 뽑아내려는 수 M을 입력받는다.
2) N 크기의 queue 배열을 생성하고 M번 반복하여 뽑아내려는 수의 위치를 받는다.
3) 우선 2번 연산을 front 값과 뽑아내려는 수의 인덱스가 같아질 때까지 반복한다. 이때, 이미 뽑아낸 수가 사이에 있으면 무시하고 넘어간다.
4) 2번 연산을 수행한 횟수가 전체 남아있는 수에서 2번 연산을 뺀 것 보다 크다면 3번 연산을 하는것이 맞기 때문에 횟수를 남아있는 수에서 2번 연산 횟수를 뺀 값으로 바꾼다.
5) 반복하면서 위의 과정을 반복하며 연산 횟수를 구한다.

3. 코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        int queue[] = new int[N];
        int front = 0;
        int end = N-1;

        int remain = N;
        int result = 0;
        for(int i=0;i<M;i++) {
            int index = Integer.parseInt(st.nextToken())-1;
            int temp = 0;
            while(front!=index) {
                end = front;
                front = (front+1)%N;
                while(remain>0 && queue[front]==1) {
                    front = (front+1)%N;
                }
                temp++;
            }
            if(temp>remain-temp) {
                temp = remain-temp;
            }
            result += temp;
            queue[front] = 1;
            remain--;
            front= (front+1)%N;
            while(remain > 0 && queue[front]==1) {
                front = (front+1)%N;
            }        
        }
        System.out.println(result);
    }
}