문제 설명

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

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

첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

분석

시작과 끝이 있는 원형 큐에서 특정 인덱스의 값을 탐색할 때 몇 번의 이동이 발생하는 지 물어보는 문제이다. 원형 큐에서는 양 방향으로 이동할 수 있는데, 최솟값을 구하라고 했으므로 방향을 선택해야 한다.

주요 포인트는, 방향을 선택하고 방향에 따라 큐를 조작하는 것이다.

1. 방향 선택
   인덱스 i에 대해, 큐의 시작과 가까우면 왼쪽으로, 끝과 가까우면 오른쪽으로 이동한다.

2. 큐 조작
   왼쪽으로 이동하는 경우, 큐의 head 값을 빼 tail에 넣는다. q.addLast(q.removeFirst)
   오른쪽으로 이동하는 경우, 반대. q.addFirst(q.removeLast)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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() + " " +  br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] indices = new int[Integer.parseInt(st.nextToken())];
        for(int i = 0; i < indices.length; i++) {
            indices[i] = Integer.parseInt(st.nextToken()) - 1;
        }

        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < N; i++) queue.add(i);

        int sum = 0;
        for(int i = 0; i < indices.length; i++) {
            int index = queue.indexOf(indices[i]);
            int fromFirst = index;
            int fromLast = queue.size() - index;
            if (fromFirst < fromLast) {
                for (int j = 0; j < fromFirst; j++)
                    queue.addLast(queue.pollFirst());
                sum += fromFirst;
            } else {
                for (int j = 0; j < fromLast; j++)
                    queue.addFirst(queue.pollLast());
                sum += fromLast;
            }
            queue.poll();
        }
        System.out.println(sum);
    }
}
![](https://velog.velcdn.com/images/studyhard/post/1b188e47-dada-4fd4-ba3a-15aaaa35a376/image.png)

마무리

처음에는 컬렉션을 사용하지 않으려고 했지만 구현이 쉽지 않았고 결국엔 java.util.LinkedList를 사용해서 풀 수 있었다.

다른 이들의 더 빠른 풀이가 있으니 참고해야겠다.