[백준] 1021번 : 회전하는 큐 (JAVA)

인간몽쉘김통통·2023년 11월 11일

덱 백준 알고리즘 자료구조 큐

백준

목록 보기

12/92

문제

이해

3개의 연산이 가능한 큐가 있다. 가능한 연산은 다음과 같다.
1. 첫 번째 원소를 뽑기
2. 왼쪽으로 한 칸 이동
3. 오른쪽으로 한 칸 이동

2, 3번째 연산은 한 칸 이동이지만 각각 특정 원소가 큐의 가장자리에 다시 삽입되기 때문에 회전이라고도 할 수 있다.

2번째 연산은 첫째 원소를 뽑아 큐의 끝에 삽입이라고 할 수 있고 3번째 연산은 마지막 원소를 뽑아 첫째에 삽입이라고도 할 수 있다.

문제는 뽑아야 하는 숫자열을 입력받아서 각 순서대로 뽑는데 필요한 2,3번 연산의 최솟값을 구해야 한다.

접근

보자마자 덱의 활용법이 떠올랐다. 덱은 양 쪽에서 삽입, 삭제가 가능한 자료구조로 회전 큐와 원리가 같다.

연산의 구현은 덱 자료구조를 이용해 쉽게 할 수 있다.
예를 들어, 2번 연산은

int tmp = deque.pollFirst();
deque.addLast(tmp);

처럼 간단하게 구현할 수 있다.

다음은 연산의 최솟값을 구해보자.

연산은 좌우 이동하는 2가지 경우밖에 존재하지 않기 때문에 구하고자 하는 원소의 위치가 어딘지 파악하면 쉽게 할 수 있다.

위와 같이 존재하는 덱에서 6을 뽑는 경우,
우선 원소 6의 위치는 덱에서 5이다. (0부터 시작하기 때문)

항상 덱은 시작 위치가 0(원소1)이기 때문에 시작 위치에서 구하는 원소의 위치와의 거리를 비교하면 된다.

2번 연산을 수행하는 경우 0에서 5로 가기위해 2번 연산을 5회 수행해야 한다. 하지만 0에서 반대 방향으로 5로 가는 경우 3번 연산을 2회만 수행하면 된다.

따라서, 다음과 같이 정리할 수 있다.

연산 구현은 덱으로
시작점에서 원소의 위치까지의 거리를 구하고 회전 방향을 결정

코드

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob1021 {
    static LinkedList<Integer> deq;
    static int N;
    static int M;
    static int ans = 0;

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

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

        deq = new LinkedList<>();

        for (int i = N; i >= 1; i--) {
            deq.addFirst(i);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());

            int target_idx = deq.indexOf(target);

            int mid_idx = (deq.size() % 2 == 0) ? deq.size() / 2 - 1 : deq.size() / 2;

            if (target_idx <= mid_idx) {
                for (int j = 0; j < target_idx; j++) {
                    cal_Left();
                    ans++;
                }
            } else {
                for (int j = 0; j < (deq.size() - target_idx); j++) {
                    cal_Right();
                    ans++;
                }
            }
            cal1();
        }

        System.out.println(ans);
    }

    static void cal1() {
        deq.poll();
    }

    static void cal_Left() {
        int tmp = deq.pollFirst();
        deq.addLast(tmp);
    }

    static void cal_Right() {
        int tmp = deq.pollLast();
        deq.addFirst(tmp);
    }
}