[백준] 회전하는 큐

1021번: 회전하는 큐 (acmicpc.net)

1021번: 회전하는 큐

 

 

🖊️문제

 

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

 

🖊️ 문제풀이

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //n, m 입력 받기
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();


        //list에 데이터 추가
        for (int i = 1; i <=n ; i++) {
            list.add(i);
        }

        //m에 맞게 데이터 입력
        //가능한 연산 수행하면서 최소 연산 횟수 도출
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            while(list.get(0) != x){
                if(list.indexOf(x) <= list.size()/2){
                    list.add(list.remove(0));
                }else{
                    list.add(0,list.remove(list.size()-1));
                }
                cnt++;
            }
            list.remove(0);
        }

        System.out.println(cnt);




    }
}