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

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

회전하는 큐를 구현하는 생각보다 간단한 문제이다.
큐에 들어가는 숫자도 1~N까지라 크게 복잡하지 않다
(다만 중요한 건 시간복잡도 인거 같다)

처음에는 단순한 배열 문제인줄 알고 ArrayList를 이용해서 구현하였다.
우선 중요한 로직은 while문 안에 있는 queueidx <= queue.size()/2 부분이다.

2번이나 3번 연산을 사용하는 최솟값을 구해야 하기 때문에 이 경우를 잘 세야 한다. 즉, 2번 연산을 쓸지, 3번 연산을 쓸지, count가 제일 적게 나오도록 해야한다.

그래서 queue의 개수가 홀수 일때, 짝수 일때로 경우의 수를 나누어 생각을 해보았다.

1. Queue가 홀수일때

queue      0     1     2     3     4
2번          0     1     2     3     4
3번          0     4     3     2     1

2. Queue가 짝수일때

queue      0     1     2     3     4     5
2번          0     1     2     3     4     5
3번          0     5     4     3     2     1

각 번호를 썼을때 각 인덱스 별로 거리가 얼마인지 세보았다.

홀수일때는 (전체 크기/2)의 인덱스 까지 2번을 쓰는게 유리했다
ex) 위 경우, 5/2 = 2, 2번 인덱스까지 2번을 쓰는게 유리

짝수일때는 (전체 크기/2)의 인덱스 에서 2번과 3번을 쓰는게 같았다

그래서 쓰기 편하도록 (전체크기/2) 인덱스까지 2번을 사용하는 것이 편하여 while문 안에 있는 queueidx <= queue.size()/2 부분을 구현하였다.

로직은 맞는거 같은데 시간 초과가 나는 것이었다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
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();
        ArrayList<Integer> queue = new ArrayList<>();
        int [] aim = new int [m]; // 뽑기 위한 숫자 배열

        for(int i=1; i<=n; i++){
            queue.add(i);
        }
        for(int i=0; i<m; i++){
            aim[i] = sc.nextInt();
        }
        int index = 0;
        int count = 0;
        int queueidx = 0;


        while (index != m){
            for(int i=0; i< queue.size(); i++){
                if(aim[index] == queue.get(i)){
                    queueidx = i;
                    break;
                }
            }

            if(aim[index] == queue.get(0)){
                queue.remove(0);
                index++;
            } else if (queueidx <= queue.size()/2) {
                int temp = queue.get(0);
                for(int i=0; i<queue.size()-1; i++){
                    queue.set(i, queue.get(i+1));
                }
                queue.set(queue.size()-1, temp);
                count++;
            } else if (queueidx > queue.size()/2) {
                int temp = queue.get(queue.size()-1);
                for(int i=1; i<queue.size(); i++){
                    queue.set(i, queue.get(i-1));
                }
                queue.set(0, temp);
                count++;
            }
        }
        System.out.print(count);
    }
}

시간 초과가 떠서 고민하다 원인을 찾아보니 ArrayList 대신 시간 초과를 줄이기 위해 Deque라는 것을 사용한다고 한다.

Deque

데크는 양방향 큐이다.
즉, 앞, 뒤 방향에서 element를 추가하거나 삭제할 수 있다.
결국 양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상자료형이다.

import java.util.*;

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> queue = new ArrayDeque<>();
        int [] aim = new int [m]; // 뽑기 위한 숫자 배열

        for(int i=1; i<=n; i++){
            queue.add(i);
        }
        for(int i=0; i<m; i++){
            aim[i] = sc.nextInt();
        }
        int count = 0;

        for (int i = 0; i < m; i++) {
            int aimIndex = getIndex(queue, aim[i]);
            if (aimIndex == 0) {
                queue.pollFirst(); // 뽑아내려는 원소가 현재 큐의 맨 앞에 있으면 그냥 뽑아냄
            } else {
                // 큐를 왼쪽 또는 오른쪽으로 회전시켜서 뽑아내기
                if (aimIndex <= queue.size() / 2) {
                    // 왼쪽으로 회전
                    while (aimIndex-- > 0) {
                        int front = queue.pollFirst();
                        queue.addLast(front);
                        count++;
                    }
                } else {
                    // 오른쪽으로 회전
                    aimIndex = queue.size() - aimIndex;
                    while (aimIndex-- > 0) {
                        int rear = queue.pollLast();
                        queue.addFirst(rear);
                        count++;
                    }
                }
                // 뽑아낸 후 맨 앞의 원소 제거
                queue.pollFirst();
            }
        }

        System.out.print(count);
    }

    private static int getIndex(Deque<Integer> queue, int i) {
        int index = 0;
        for(int num : queue){
            if(num == i){
                break;
            }
            index++;
        }
        return index;
    }
}

Deque를 이용하여 첫번째 값을 뽑아내는 pollFirst() 함수를 이용하여 시간복잡도를 줄여 구현했다.