[BOJ_1021] 회전하는 큐 Java (덱)

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

1021번: 회전하는 큐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m;
    static ArrayList<Integer> q = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        for(int i=0; i<=n; i++) {
            q.add(i);
        }

        stk = new StringTokenizer(br.readLine());
        int count = 0;

        for(int i=0; i<m; i++) {
            int target = Integer.parseInt(stk.nextToken());

            // target이 현재 맨 앞
            if(q.get(1) == target) {
                q.remove(1);
                continue;
            }

            int index = q.indexOf(target);
            int frontSteps = q.indexOf(target) - 1; // 앞을 옮기는 것
            int backSteps = q.size()-1-index; // 뒤를 옮기는 것

            // 앞을 옮기는 게 빠름
            if(frontSteps <= backSteps) {
                // target이 맨앞에 올때까지 2번 연산
                while(q.get(1) != target) {
                    int temp = q.remove(1);
                    q.add(temp);
                    count++;
                }
                q.remove(1);
            }
            // 뒤를 옮기는 게 빠름
            else {
                // target이 맨앞에 올때까지 3번 연산
                while(q.get(1) != target) {
                    int temp = q.remove(q.size()-1);
                    q.add(1, temp);
                    count++;
                }
                q.remove(1);
            }
        }

        System.out.println(count);
    }
}

자료구조 문제입니다.
큐의 앞과 뒤에서 모두 삽입/삭제가 가능한 덱 구조를 사용하여 풀면 됩니다.

다만 자바의 Deque는, 인덱스 접근이 안 된다는 불편함이 있기에 ArrayList를 사용했습니다.

 

---

 

✨ 로직 설명

1. 현재 뽑아내야하는 원소를 target으로 둡니다.
2. target을 뽑기 위해서 앞의 원소를 뒤로 보내는 연산을 해야할지 / 뒤의 원소를 앞을 보내는 연산을 해야할지 결정합니다. 둘 중 더 적은 수의 연산을 해도 되는 쪽으로 선택합니다.
3. 이를 frontSteps, backSteps라고 표현했습니다.
4. frontSteps <= backSteps 에서 등호를 함께 사용한 이유는, 앞쪽에 원소가 위치한 경우 뒤쪽에 위치한 경우보다 한 번 연산을 적게 할 수 있기 때문입니다.
   https://www.acmicpc.net/board/view/24395
   이 게시글이 많은 도움이 되었습니다.