Queue / Deque: 백준 1021번 회전하는 큐

• 출처: https://www.acmicpc.net/problem/1021

문제 설명

결국 제시된 3가지 연산을 이해하는 것이 중요하다.

1. 첫 번째 원소를 뽑아낸다. 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.

2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.

3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

앞뒤로 값을 한 칸씩 옮기거나 지울 수 있다는 점에서 "Deque"를 떠올릴 수 있다.

• 1번 연산은 결국 removeFirst()
• 2번 연산은 deque.addLast(deque.removeFirst())
• 3번 연산은 deque.addFirst(deque.removeLast())

의 개념과 연결될 수 있을 것이다.

코드 설명

1번 연산은 바로 수행하면 되지만, 2,3번 연산은 수행하기 전에 2번 연산에 해당하는지, 3번 연산에 해당하는지 판단할 필요가 있다.

그래서, distance라는 개념을 도입하여 왼쪽까지의 거리, 오른쪽까지의 거리를 계산하였다. 이를 통해 더 거리가 짧은 쪽으로 이동하면 될 것이다.

import java.io.IOException;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.IntStream;

import static java.lang.Math.abs;

public class Q2 {
    public static Integer checkDistance(int item, int target, LinkedList<Integer> deque) {
        int distance = abs(deque.indexOf(item) - deque.indexOf(target));
        int halfIndex = deque.size() / 2;
        if (distance > halfIndex) {
            distance = deque.size() - distance;
        }
        return distance;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        LinkedList<Integer> deque = new LinkedList<Integer>();

        int N = sc.nextInt();
        int M = sc.nextInt();
        int cnt = 0;
        int target = 0;

        IntStream.range(1, N+1).forEach(deque::add);

        int[] seq = new int[M];

        for(int i = 0; i < M; i++) {
            seq[i] = sc.nextInt();
        }

        for (int item: seq){
            target = (int) deque.getFirst();
            int distance = checkDistance(item, target, deque);
            if (distance == 0){
                deque.getFirst();
            } else if (abs(deque.indexOf(item) - deque.indexOf(target)) <= deque.size() / 2) {
                for (int i = 0; i < distance; i++) {
                    deque.addLast(deque.removeFirst());
                }
            } else {
                for (int i = 0; i < distance; i++){
                    deque.addFirst(deque.removeLast());
                }
            }
            cnt += distance;
            deque.removeFirst();
        }
        System.out.println(cnt);
    }
}

소감

처음에 indexOf()를 쓸 수 없다고 생각해서 구현에 시간이 다소 오래 걸렸다. 해당 기능에 대한 숙지가 필요할 것 같다..!