회전하는 큐 - 1021

문제

풀이

import java.util.*;

//백준 - 회전하는 큐 - S3
public class ex1021 {

    static LinkedList<Integer> list = new LinkedList<>();

    public static int solution(int n, int m , int[] arr){
        int answer=0;

        for(int i=1; i<=n; i++) list.add(i);

        for(int x : arr){
            int index = list.indexOf(x);
            int hdex = list.size()/2;

            if(index <= hdex){
                while(x!=list.getFirst()){
                    list.add(list.removeFirst());
                    answer++;
                }
            }
            else{
                while(x!=list.getFirst()){
                    list.addFirst(list.removeLast());
                    answer++;
                }
            }
            list.remove();
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[m];
        for(int i=0; i<m; i++){
            arr[i]=sc.nextInt();
        }
        System.out.println(solution(n,m,arr));
    }
}

풀이

1. 큐는 원래 FIFO성질을 가진다. 이 문제는 양방향 큐를 요구하는 문제이다.
2. 이 문제를 해결하기 위해서는 Index를 알아내는 메서드가 필요한데 Q에는 없어서 LinkedList<인티저> list = new LinkedList<>(); 를 선언해서 문제를 해결했다.
3. 우선 뽑으려고 하는 해당 요소 x를 젤 앞으로 데리고 와야한다. x의 위치를 파악해서 그 위치가 절반보다 적으면 왼쪽으로 이동시키고 , 절반 보다 크면 오른쪽으로 이동시키면서 그 최솟값으로 이동시킨 횟수를 answer로 하여 리턴한다. 그 후에 해당 요소 x는 뽑는개념이라 remove()시켜준다.