[백준] 1021번: 회전하는 큐 - Java

문제

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

주어진 수열에서 숫자를 하나씩 뽑아내야 하는데, 이때 큐를 왼쪽 또는 오른쪽으로 회전시켜 원하는 숫자를 가장 앞에 놓는 작업을 최소화해야 합니다. 주어진 수열을 순서대로 뽑아내기 위해 큐를 회전하는 최소 횟수를 구하는 것입니다.

 

접근 방법

덱(Deque) 자료구조 사용

• 덱은 큐와 스택의 특성을 모두 갖춘 자료구조로, 양 끝에서 삽입과 삭제가 가능합니다. 이를 통해 큐의 좌우 회전을 쉽게 구현할 수 있습니다.

최소 회전 횟수 계산

• 현재 뽑아내려는 숫자의 위치에 따라 왼쪽으로 회전하는 것이 빠를지, 오른쪽으로 회전하는 것이 빠를지 판단합니다.
• 왼쪽으로 회전할 때와 오른쪽으로 회전할 때의 횟수를 비교하여 더 적은 횟수만큼 회전합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    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를 사용하여 큐를 구현
        Deque<Integer> deque = new LinkedList<>();

        // 1부터 N까지의 숫자를 덱에 삽입
        for (int i = 1; i <= N; i++) {
            deque.offer(i);
        }

        int[] target = new int[M];
        // 뽑아낼 수들의 위치를 배열에 저장
        st = new StringTokenizer(br.readLine()); // 새로운 입력을 받음
        for (int i = 0; i < M; i++) {
            target[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0; // 최소 회전 횟수

        for (int i = 0; i < M; i++) {
            int targetIndex = 0;
            // 덱에서 target[i]의 위치를 찾음
            for (int num : deque) {
                if (num == target[i]) {
                    break;
                }
                targetIndex++;
            }

            int leftRotation = targetIndex; // 왼쪽으로 회전할 때의 횟수
            int rightRotation = deque.size() - targetIndex; // 오른쪽으로 회전할 때의 횟수

            // 더 적은 회전수를 선택하여 회전
            if (leftRotation <= rightRotation) {
                // 왼쪽으로 회전
                for (int j = 0; j < leftRotation; j++) {
                    deque.offerLast(deque.pollFirst());
                    count++;
                }
            } else {
                // 오른쪽으로 회전
                for (int j = 0; j < rightRotation; j++) {
                    deque.offerFirst(deque.pollLast());
                    count++;
                }
            }

            // 숫자를 덱에서 제거
            deque.pollFirst();
        }

        System.out.println(count);
    }
}

메모리:14312kb 시간:100ms