[Baekjoon] 1021번 회전하는 큐 (Java)

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

1021번: 회전하는 큐

 

회전하는 큐 문제 Java로 풀이하겠습니다.

 

이 문제는 큐에서 원소를 뽑아내는 연산을 최소화하기 위해 어떻게 큐의 상태를 조작해야 하는지를 찾는 문제로 보입니다.

 

다음과 같은 알고리즘으로 문제를 해결할 수 있습니다.

1. 큐의 첫 번째 원소를 뽑아내는 연산을 수행합니다.
2. 원하는 위치에 도달할 때까지 큐를 왼쪽으로 이동하며 연산을 수행합니다.
   이때, 왼쪽 이동 연산 횟수가 원하는 위치에 도달하기 위한 연산 횟수가 됩니다.
3. 원하는 위치에서 첫 번째 원소를 뽑아내는 연산을 수행합니다.

 

저는 다음과 같이 풀이하였습니다.

 

먼저 문제에서 제시한 대로 양방향 순환 큐를 구현하기 위한 인터페이스 Deque를 사용하겠습니다.

Deque는 큐의 양쪽 끝에서 삽입과 삭제를 모두 처리할 수 있는 큐로, 큐의 양 끝에서 빠르게 삽입과 삭제를 수행할 수 있습니다.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 큐의 크기
        int m = sc.nextInt(); // 뽑아내려는 수의 개수

        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            deque.add(i);
        }

        int count = 0;

        for (int i = 0; i < m; i++) {
            int index = sc.nextInt(); // 뽑아내려는 수의 위치
            int left = 0;
            int right = 0;

            while (deque.peek() != index) {
                deque.addLast(deque.removeFirst());
                left++;
            }

            right = deque.size() - left;

            count += Math.min(left, right);
            deque.removeFirst();
        }

        System.out.println(count);
        sc.close();
    }
}

 

1. 사용자의 입력을 받기 위한 Scanner 객체를 생성하여  n에 큐의 크기를 입력받고 m에 뽑아내려는 수의 개수를 입력받습니다.
2. 1부터 N까지 숫자를 갖는 큐 deque를 선업 합니다.
3. 뽑아내려는 수의 위치를 입력받아 해당 숫자를 뽑을 때까지 왼쪽과 오른쪽으로 큐를 이동시킵니다.
4. 이동하는 횟수를 세어 2번과 3번 연산의 총 횟수를 구합니다.
5. 총 횟수를 출력합니다.

 

위의 코드는 큐의 크기와 뽑아내려는 수의 위치에 따라 큐의 왼쪽 또는 오른쪽으로 이동하여 값을 뽑아내는 과정을 반복합니다.

그리고 최소 이동 횟수를 구하여 2번과 3번 연산의 총 횟수를 구한 후 마지막으로 그 값을 출력합니다!

 

다른 이견이 있으시면 자유롭게 댓글 남겨주세요