Queue의 활용 - BOJ 1021 회전하는 큐

문제

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

 

접근 방법

• 양방향으로 데이터가 삽입 삭제가 가능한 큐를 이용하여 회전이 최소화되도록 요소들을 빼는 문제이다.
• 문제에서 자료구조의 첫 번째 원소를 가지고 뺄지 말지를 판단하는 것에서 큐라는 자료구조가 생각날 수 있으나 회전의 관점에서 큐를 사용하여 회전시키는 건 조금 귀찮을 여지가 있다(역방향 회전에서 특히)
• 따라서 해당 문제에 사용할 자료구조는 큐보단 덱이 조금 더 구현하기가 깔끔하다.
• 회전의 경우 정방향과 역방향 회전이 존재하는데 이를 사용하는 기준을 먼저 잡아야 어떤 상황에서 어떤 방향으로 회전을 시킬 것인지를 판단할 수 있을 것이다.
  • 문제에서 전체 회전 횟수가 "최소"가 되야 한다고 했기 때문에 다음과 같은 방식으로 방향을 결정하는 것이 좋다.
    • 입력으로 들어오는 각 수들은 빼낼 원소의 위치를 말한다. 이때 위치를 찾고 그 위치가 덱의 길이 - 위치 보다 크다면, 해당 위치가 덱의 끝부분에 더 가깝다는 것이므로 tail의 원소가 front로 가는 정방향 회전을 수행한다.
    • 만약 반대로 덱의 길이 - 위치 > 위치 라면 해당 위치가 덱의 시작 부분에 더 가깝다는 것이므로 front의 원소가 tail로 가는 역회전이 수행되게 한다.
• 얼핏 보면 왜 그런지 이해가 가지 않을 수 있다. 간단한 예제를 통해 알아보자 다음 TC를 사용할 것이다.

10 3
2 9 5

• 덱의 초기 상태는 아래 사진과 같다.

초기 Deque의 사진

• 이때 두 번째 위치의 원소를 제거해야 한다. 지금은 Deque가 초기 상태이므로 2를 빼내면 된다.
  • 이때, 2는 앞에 1이 존재하여 빼내기가 불가능하므로 회전을 수행해야 한다. 2의 index, 즉 현재 Deque에 위치하는 자리는 2이다.
  • 이제 이 index가 Deque에서 어느 부분에 위치하는지를 찾아야 한다. 정중앙을 기점으로 head에 더 가까운지, tail에 더 가까운지 알아야 회전의 방향을 결정할 수 있기 때문이다.

• 기준점이 되는 덱의 크기 - 현재 원소가 덱에 위치하는 자리 가 현재 자리하는 위치보다 크다면, 해당 위치는 앞쪽에 위치하는 것이다.
  • 이렇게 되는 이유는 size()가 처음부터 끝까지를 기준으로 하기 때문에 size()에서 현재 위치를 뺀다면 Deque의 끝을 기준으로 얼마나 떨어져 있는지를 나타내는 "거리"의 개념이 되기 때문이다.
• Deque.size() - index > index이므로 역방향 회전을 수행한다. 상한선은 해당 Deque의 front가 2가 될 때 까지가 된다.
• 이후 Deque의 상태는 아래와 같다.

• 이다음은 초기 큐에서 9번째 위치에 존재하는 원소를 빼낼 차례이다. 하지만 현재 회전으로 인하여 위치가 섞였기 때문에 현재 Deque에서 초기 Deque의 9번째 원소가 어디에 위치하는지를 찾아야 한다.

• 동일하게 index를 찾은 뒤 Deque의 길이를 사용하여 Deque의 Front에 가까운지 tail에 가까운지를 확인한다. 여기서는 index가 더 크므로 tail에 가깝다는 의미이며 이로 인해 정방향 회전을 수행하게 된다.
• 이와 같이 위치를 확인하여 회전 방향을 결정하고, 회전하면서 회전 횟수를 1씩 올려주면 끝이다. 이를 수행한 답안 코드는 아래와 같다.

 

 

답안 코드

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

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

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

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

        for(int i = 1; i <= N; i++){
            deque.addLast(i);
        }

        st = new StringTokenizer(br.readLine());
        int ans = 0;

        while(st.hasMoreTokens()){
            int key = Integer.parseInt(st.nextToken());
            int index = 0;

            for (Integer element: deque) {
                if (element == key){
                    break;
                }

                index++;
            }

            while(deque.peekFirst() != key){
                if (deque.size() - index < index){
                    deque.addFirst(deque.pollLast());
                    ans++;
                } else{
                    deque.addLast(deque.pollFirst());
                    ans++;
                }
            }
            deque.pollFirst();
        }

        System.out.println(ans);
    }
}