BOJ 1021번: 회전하는 큐

문제

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

풀이

1. 앞뒤로 삽입, 삭제가 가능하다 => Deque 개념 활용
2. 큐에 처음 포함되어 있던 수 = 큐의 크기 = N => 큐에 1~N까지 삽입한다.
3. M개만큼 뽑아낼 값을 입력받는다.
4. 연산의 최소값을 구한다.
   • 큐의 가운데 인덱스를 기준으로 구하려는 값이
     • 가운데보다 왼쪽에 존재할 경우, 큐를 왼쪽으로 한 칸씩 이동
       • 왼쪽으로 이동하다가 원하는 값이 나오면 
         • 반복 종료 후 poll
     • 가운데보다 오른쪽에 존재할 경우, 큐를 오른쪽으로 한 칸씩 이동
       • 오른쪽으로 이동하다가 원하는 값이 나오면
         • 반복 종료 후 poll

 

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));
        LinkedList<Integer> dq = new LinkedList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());


        for(int i=1;i<=N;i++) {
            dq.add(i);
        }

        ArrayList<Integer> arr = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++) {
            int n = Integer.parseInt(st.nextToken());
            arr.add(n);
        }

        int cnt = 0;
        for(int i: arr) {
            int idx = dq.indexOf(i);
            int mid = dq.size() / 2;

            if(idx > mid) {
                while(i != dq.getFirst()) {
                    cnt++;
                    dq.addFirst(dq.removeLast());
                }
            }
            else {
                while(i != dq.getFirst()) {
                    cnt++;
                    dq.addLast(dq.removeFirst());
                }
            }
            dq.removeFirst();
        }
        System.out.println(cnt);
    }
}