Java 1021 회전하는 큐

 

 

풀이 :
큐 자료구조는 FIFO으로 먼저 들어온 것이 먼저 나가게 된다. 문제에서는 순환하는 큐에서 찾고자 하는 최소한의 연산을 통해 찾으라고 하고 있다. LinkedList로 큐를 구현하여 원소를 회전할 때 왼쪽으로 회전해야한다면 가장 앞의 원소를 pop하고 가장 끝으로 push하는 식으로 진행하였다.

최소값을 구하는 게 문제였으니 찾고자 하는 원소의 index와 큐의 가운데 index 값을 비교하여 이보다 크면 3번 연산을 크지 않거나 같다면 2번 연산을 통하여 큐를 회전시켜주고 result를 1씩 증가하여주어 최소 연산값을 구할 수 있었다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

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

        int result = 0;

        LinkedList<Integer> deque = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            deque.add(i);
        }

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(st.nextToken());
            int half = deque.size()/2;
            int index = deque.indexOf(a);

            if(deque.peekFirst() == a){
                deque.pollFirst();
                continue;
            }

            if(index > half){
                index = deque.size() - index;
                for(int j = 0; j < index; j++){
                    deque.offerFirst(deque.pollLast());
                    result++;
                }
                deque.pollFirst();
            }else if(index <= half){
                for(int j = 0; j < index; j++){
                    deque.offerLast(deque.pollFirst());
                    result++;
                }
                deque.pollFirst();
            }
        }

        System.out.println(result);
    }
}