[JAVA] 백준 알고리즘 1021번 (회전하는 큐)

문제

---

이번에 다뤄볼 문제는 1021번 문제 '회전하는 큐'입니다.

문제에서 연습해야 하는key-point는 Deque(덱)입니다.

 

Deque이란 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태입니다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있고 큐와 스택을 합친 형태로 생각할 수 있습니다.

흔히 우리가 카드게임을 할 때 카드덱 이라고 부르는 그 덱과 유사한 개념이라고 생각할 수 있습니다.

 

우선 문제를 천천히 분석해 보겠습니다.

문제에서 결과로 원하는 값은 주어진 숫자를 순서대로 뽑기 위한 큐(카드덱)의 움직임 최솟값 입니다.

예제 입력 2를 통해 문제에서 원하는 값을 가져오는 과정에 대해 살펴보겠습니다.

주어진 연산과 상황은 아래와 같습니다.

[연산 3가지]

1. 맨 앞의 카드를 뽑는다

2. 맨 앞의 카드를 맨 뒤로 이동시킨다.

3. 맨 뒤의 카드를 맨 앞으로 이동시킨다.

--

카드덱 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

뽑을 숫자 카드 = 2, 9, 5

카드덱을 움직인 횟수 = 0 (2번 3번의 연산에 대한 횟수)

 

여기서 첫번째로 뽑아야 하는 카드는 2입니다. 우리는 2를 뽑기 위해서 카드 1을 맨 뒤로 보내고 가져오면 된다는 것을 바로 계산 할 수 있습니다. 그럼 한번 움직여보겠습니다.

카드덱 = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]

뽑을 숫자 카드 = 2, 9, 5

카드덱을 움직인 횟수 = 1

 

이제 카드 2가 맨 앞에 있기 때문에 문제에 주어진 1번 연산을 활용해 첫번째 원소를 뽑도록 하겠습니다.

여기까지 진행했을때 상황은 아래와 같습니다.

카드덱 = [3, 4, 5, 6, 7, 8, 9, 10, 1]

뽑을 숫자 카드 = 9, 5

카드덱을 움직인 횟수 = 1

 

카드덱에서 2가 사라졌고, 뽑을 숫자 카드에서도 2는 해결되어 이제 9를 뽑을 차례임을 알 수 있습니다. 그럼 우리가 9를 뽑으려면 어떻게 해야 할까요? 앞에서부터 카드를 빼서 뒤로 옮기는 과정보다, 뒤에서 카드를 뽑아 맨 앞에 추가해주면 더 적은 횟수로 9를 덱의 맨 앞으로 옮길 수 있다는걸 우린 바로 생각할 수 있습니다.

이때 이번 문제의 핵심이 드러납니다. 우리는 어떻게 9를 카드덱의 맨 앞으로 가져오려면 뒤에서부터 빼서 가져오면 된다고 생각했을까요?

그건 바로 카드덱의 중간을 기준으로 9가 뒤쪽에 있기 때문입니다. 즉, 중간을 기준으로 뽑으려는 카드가 덱의 앞쪽에 있다면 2번 연산을 수행하고 반대로 뒤쪽에 있다면 3번 연산을 수행하면 된다는 이야기입니다.

따라서 3번 연산을 총 세번 수행하면 9가 맨 앞으로 오게 될 것입니다.

카드덱 = [9, 10, 1, 3, 4, 5, 6, 7, 8]

뽑을 숫자 카드 = 9, 5

카드덱을 움직인 횟수 = 4

 

이제 카드 9가 맨 앞에 있기 때문에 문제에 주어진 1번 연산을 활용해 첫번째 원소를 뽑도록 하겠습니다.

여기까지 진행했을때 상황은 아래와 같습니다.

카드덱 = [10, 1, 3, 4, 5, 6, 7, 8]

뽑을 숫자 카드 = 5

카드덱을 움직인 횟수 = 4

 

이제 위 과정을 토대로 다음 뽑을 숫자 카드인 5를 얻기 위해서는 3번 연산을 4번 더 수행하면 5가 카드덱의 맨 앞으로 이동한다는 사실을 알 수 있습니다. 따라서 예제 입력 2에 대한 출력값이 8이 되는겁니다.

 

우리는 자바로 문제를 해결하고 있기 때문에 LinkedList를 활용하여 Deque를 쉽게 구현할 수 있습니다.

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        LinkedList<Integer> deque = new LinkedList<>();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            deque.offer(i);
        }

        int m = in.nextInt();
        int[] targetArray = new int[m];
        for (int i = 0; i < m; i++) {
            targetArray[i] = in.nextInt();
        }

        int count = 0;

        for (int target : targetArray) {
            int targetIndex = deque.indexOf(target);
            int indexOfHalfDeque = deque.size() / 2;

            if (targetIndex <= indexOfHalfDeque) {
                while (target != deque.getFirst()) {
                    deque.addLast(deque.removeFirst());
                    count++;
                }
            } else {
                while (target != deque.getFirst()) {
                    deque.addFirst(deque.removeLast());
                    count++;
                }
            }
            deque.pollFirst();
        }

        System.out.println(count);
    }
}

 

1021번: 회전하는 큐