BOJ 1021. 회전하는 큐

BOJ 1021. 회전하는 큐

풀이

왼쪽 오른쪽으로 회전하는 것은 덱을 이용하여 양쪽에서 삽입 삭제를 해주면 쉽게 구현이 가능하다.
덱에 1~n 까지 삽입한 후, 원하는 값이 나온다면 덱에서 poll,
원하는 값이 나오지 않는다는 왼쪽 또는 오른쪽으로 Shift해준다.
현재 인덱스가 덱사이즈의 절반이상인지 이하인지 판단하여 더 가까운 쪽으로 Shift할 방향을 결정한다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str1 = br.readLine().split(" ");
        int n = Integer.parseInt(str1[0]);
        int m = Integer.parseInt(str1[1]);

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

        for (int i = 1; i <= n; i++) deque.add(i);

        String[] str2 = br.readLine().split(" ");
        int result = 0;
        for (int z = 0; z < m; z++) {
            int number = Integer.parseInt(str2[z]);
            while (true) {
                int idx = 0;
                Iterator<Integer> it = deque.iterator();
                while (it.hasNext()) {
                    if (it.next() == number) break;
                    idx++;
                }
                if (idx == 0) {
                    deque.pollFirst();
                    break;
                } else if (deque.size() / 2 >= idx) {
                    deque.addLast(deque.pollFirst());
                    result++;
                } else {
                    deque.addFirst(deque.pollLast());
                    result++;
                }
            }
        }
        System.out.println(result);
    }
}