백준 1021 회전하는 큐 Java: 한 개의 Deque로 최소 이동 계산

백준 1021번을 처음 읽었을 때는 두 번째 예제가 왜 그렇게 움직이는지 헷갈렸다. 원문에는 시계 방향과 반시계 방향으로 돌린 횟수를 각각 구해 더 작은 값을 선택하면 된다고 정리해 두었다.

• 백준 1021번 회전하는 큐

방향별 Deque를 두 개 만들 필요는 없다. 현재 큐에서 target의 왼쪽 거리를 찾으면 오른쪽 거리는 현재 크기 - 왼쪽 거리다. 더 짧은 방향으로 실제 큐 하나만 회전하고 target을 꺼내면 된다.

이동 횟수를 index로 바꾸기

현재 큐가 다음과 같다고 하자.

front → [1, 2, 3, 4, 5] ← back
target = 4

4의 왼쪽 index는 3이다.

• 왼쪽 회전: 3회
• 오른쪽 회전: 5 - 3 = 2회

따라서 오른쪽으로 두 번 회전한 뒤 맨 앞의 4를 꺼낸다. target을 꺼내는 첫 번째 연산은 이동 횟수에 포함하지 않는다.

두 방향의 거리가 같으면 어느 쪽을 선택해도 이후 큐 상태는 같다. target 앞뒤의 원형 순서가 유지된 채 target만 제거되기 때문이다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int queueSize = Integer.parseInt(tokenizer.nextToken());
        int targetCount = Integer.parseInt(tokenizer.nextToken());

        Deque<Integer> deque = new ArrayDeque<>();
        for (int value = 1; value <= queueSize; value++) {
            deque.addLast(value);
        }

        int moves = 0;
        tokenizer = new StringTokenizer(reader.readLine());

        for (int targetIndex = 0; targetIndex < targetCount; targetIndex++) {
            int target = Integer.parseInt(tokenizer.nextToken());
            int leftMoves = indexOf(deque, target);
            int rightMoves = deque.size() - leftMoves;

            if (leftMoves <= rightMoves) {
                for (int move = 0; move < leftMoves; move++) {
                    deque.addLast(deque.removeFirst());
                }
                moves += leftMoves;
            } else {
                for (int move = 0; move < rightMoves; move++) {
                    deque.addFirst(deque.removeLast());
                }
                moves += rightMoves;
            }

            deque.removeFirst();
        }

        System.out.println(moves);
    }

    private static int indexOf(Deque<Integer> deque, int target) {
        int index = 0;
        for (int value : deque) {
            if (value == target) {
                return index;
            }
            index++;
        }
        throw new IllegalStateException("target not found");
    }
}

원문의 두 Deque 풀이를 줄인 이유

원문은 왼쪽 회전용 큐와 오른쪽 회전용 큐를 따로 유지했다. 각 target을 제거한 뒤 두 큐가 우연히 같은 원형 순서로 맞춰지기 때문에 동작할 수 있지만, 매 단계 두 큐를 모두 끝까지 회전시킨다. 두 상태가 계속 같다는 사실도 별도로 확인해야 한다.

한 개의 큐에서 target 위치를 찾고 짧은 방향만 실행하면 상태의 기준점이 하나다. 문제의 제한에서는 위치를 찾는 O(N) 순회도 충분하며, 전체 시간 복잡도는 O(NM) 이내다.

기본 queue 구현은 백준 18258 큐 2, 입력 event를 FIFO buffer로 옮기는 예시는 백준 15828 Router에서 비교할 수 있다.

검증 범위

Java source를 수동 검토했다. 첫 원소, 마지막 원소, 양쪽 거리가 같은 원소와 연속 target 제거를 포함해 N≤8의 가능한 target 순서를 완전 탐색하고 최단 이동 기준값과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.