[백준] 1021 회전하는 큐 자바(Java)

문제설명

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

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

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

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

 

 

입력

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

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

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

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

 

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

 

 

통과한 코드 ✅

import java.util.*;
import java.io.*;

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());

        LinkedList<Integer> deque=new LinkedList<>();

        int cnt=0;

        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            deque.offer(i);
        }

        int sel[]=new int[n]; // 뽑고자 하는 수들을 담은 배열

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

        for(int i=0; i<m; i++){
            int target=deque.indexOf(sel[i]);
            int half;

            if(deque.size()%2==0){
                half=deque.size()/2-1;
            }else{
                half=deque.size()/2;
            }

            if(target<=half){
                // 중간 지점보다 원소의 위치가 앞에 있는 경우
                // 타겟보다 앞에 있는 원소들을 모두 뒤로 보냄
                for(int j=0; j<target; j++){
                    int tmp=deque.pollFirst();
                    deque.offerLast(tmp);
                    cnt++;
                }
            }else{
                // 중간 지점보다 원소의 위치가 뒤에 있는 경우
                // 타겟을 포함한 뒤에 있는 원소들을 모두 앞으로 보냄
                for(int j=0; j<deque.size()-target; j++){
                    int tmp=deque.pollLast();
                    deque.offerFirst(tmp);
                    cnt++;
                }
            }
            deque.pollFirst(); // 연산 끝나면 맨 앞 원소 삭제
        }
        System.out.println(cnt);
    }
}