회전하는 큐

Stack, Queue, Deque 모두 선형 리스트로서 순차적으로 메모리를 할당받도록 내부에 구현됩니다. 각각의 차이를 만드는 부분은 데이터 삽입, 삭제 방식이 다르다는 것입니다. 그에 따라서 각각이 만들어 낼 수 있는 순열(permutation)도 서로 다릅니다.

문제에서 묘사하고 있는 회전하는 큐(Cicular Queue)를 어떻게 구현할 수 있는 가에 대한 질문도 마찬가지로 위 맥락에서 봤을 때 같은 순열을 만들 수 있겠는 가에 대한 질문으로 치환할 수 있습니다.

한 예로 왼쪽이 더 오른쪽보다 선입되었다고 가정했을 때(반대로 가정하더라도 결과는 동일함) [a, b, c, d, e]배열을 [b, c, d, e, a]로 바꿨다가 다시 원래 배열로 돌아가는 형태의 재배열을 Stack과 Queue은 구조적으로 할 수가 없지만 저들의 상위 알고리즘이라고 할 수 있는 Deque은 가능합니다.

아래의 코드는 Java의 Deque을 활용해서 위 문제를 해결하는 과정을 보여줍니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
    static private <T> int getDistanceFromFirst (Deque<T> deque, T target) throws RuntimeException {
        int dequeSize = deque.size();
        for (int i = 1; i <= dequeSize; ++i) {
            if (Objects.equals(deque.pollFirst(), target)) {
                return i;
            }
        }
        throw new RuntimeException("!deque.contains(target)");
    }

    static private <T> int getDistanceFromLast (Deque<T> deque, T target) throws RuntimeException {
        int dequeSize = deque.size();
        for (int i = 1; i <= dequeSize; ++i) {
            if (Objects.equals(deque.pollLast(), target)) {
                return i;
            }
        }
        throw new RuntimeException("!deque.contains(target)");
    }

    static public void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        int numElements = Integer.parseInt(st.nextToken());
        int numPickups = Integer.parseInt(st.nextToken());

        int[] pickups = new int[numPickups];
        st = new StringTokenizer(bf.readLine(), " ");
        for (int i = 0; i < numPickups; i++) {
            pickups[i] = Integer.parseInt(st.nextToken());
        }

        // Positions in the sequence
        Deque<Integer> circularQueue = new ArrayDeque<>();
        IntStream.iterate(1, n -> n + 1).limit(numElements).forEach(circularQueue::add);

        int sum = 0;
        for (int pickup : pickups) {
            int distToFirst = getDistanceFromFirst(new ArrayDeque<>(circularQueue), pickup);
            int distToLast = getDistanceFromLast(new ArrayDeque<>(circularQueue), pickup);

            if (distToFirst <= distToLast) {
                for (int j = 1; j <= distToFirst; ++j) {
                    if (pickup == circularQueue.getFirst()) {
                        circularQueue.pollFirst();
                        continue;
                    }


                    circularQueue.addLast(circularQueue.pollFirst());
                    sum += 1;
                }
            }
            else { // distToFirst > distToLast
                for (int j = 1; j <= distToLast; ++j) {
                    if (pickup == circularQueue.getLast()) {
                        circularQueue.pollLast();
                        sum += 1;
                        continue;
                    }

                    circularQueue.addFirst(circularQueue.pollLast());
                    sum += 1;
                }
            }
        }
        System.out.print(sum);
    }
}

백준: http://boj.kr/10289cccb84a4c9088938fb0e91637be