[BOJ] 1021 회전하는 큐 - JAVA

1. 문제

---

2. 풀이

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

public class BOJ_1021_회전하는큐 {
    public static void main(String[] args) throws IOException {
        //입력
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

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

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            queue.offer(i);
        }

        st = new StringTokenizer(in.readLine());

        //탐색
        int sum = 0;
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            int count = 0;
            while (num != queue.peek()) {
                queue.offer(queue.poll());
                count++;
            }
            sum += Math.min(count, queue.size() - count);
            queue.poll();
        }

        //출력
        System.out.println(sum);
    }
}

덱으로 풀려다가 한 방향으로만 뽑아도 되는 걸 깨닫고 큐로 변경했다. (그래서 ArrayDeque<>()으로 객체 생성한 게 남아있음)

"뽑고 싶은 수"가 맨 앞에 있어야 뽑을 수 있으므로, 어느 쪽으로 큐를 회전했든 뽑기 직전의 큐 상태는 동일하다. 

따라서 왼쪽에서만(먼저 입력받은 숫자부터) pop시키고, "그 횟수"와 "큐의 현재 길이-횟수"를 비교한다. 

처음에는 "큐의 현재 길이-횟수-1"과 비교해야 하는 줄 알고 풀었다가 계속 틀렸는데, 생각해보니 이 문제는 뽑으려는 수가 맨 앞에 있어야 하므로 오른쪽(뒤)에서 뽑을 때는 뽑으려는 수도 앞으로 올 수 있도록 pop 시켜줘야 한다. 

---

3. 결과

아래(예전) 코드는 다 입력받은 후 비교하는 코드였다. 당연하지만 입력받으면서 그때그때 탐색하는 방식이 훨씬 빠르다.