[백준] - 회전하는 큐

회전하는 큐

풀이

큐의 크기 N이 주어질 때, N개 안에서 최소한의 시프트로 수를 뽑아내는 문제이다.
뽑아내려는 수의 위치를 알고 있을 때, 전체 큐의 사이즈에서
1) 중간위치보다 왼쪽에 있다면 왼쪽 시프트
2) 중간위치보다 오른쪽에 있다면 오른쪽 시프트
하여 뽑고자 하는 원소를 큐의 가장 앞에 위치시키는 것이 최소한의 횟수로 시프트를 시키는 것이라고 생각하였다.

코드

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

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());

        List<Integer> list = new ArrayList<>();

        for(int i = 1; i <= N; i++){
            list.add(i);
        }

        int answer = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            int ele = Integer.parseInt(st.nextToken());
            // 뽑고자 하는 원소의 위치찾기
            int idx = list.indexOf(ele);

            // 오른쪽으로 시프트해서 뽑는게 더 빠름(3번연산)
            if(idx >= (list.size() + 1) / 2){
                for(int j = 0; j < list.size() - idx; j++){
                    answer++;
                    list.add(0, list.remove(list.size() - 1));
                }
            }
            // 왼쪽 시프트해서 뽑는게 더 빠름(2번연산)
            else{
                for(int j = 0; j < idx; j++){
                    answer++;
                    list.add(list.remove(0));
                }
            }
            // 정답뽑기(1번연산)
            list.remove(0);
        }
        System.out.println(answer);
    }
}