백준 1021번: 회전하는 큐

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

1021번: 회전하는 큐

풀이 접근법 : 1~N 까지 queue에서 target을 찾을 때 까지 leftshift, rightshift 하여 count를 하나씩 증가한다.

 

 deque로 구현하여 start와 end에서 데이터를 뽑아서 shift 할 수 있음

 Index를 편하게 구하는 방법을 알지 못해, 0부터 peek()함수로 비교하면서 index를 구함

 

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));
        String[] number = br.readLine().split(" ");
        int num = Integer.parseInt(number[0]);
        int m = Integer.parseInt(number[1]);
        int[] outNum = new int[m];
        int answer = 0;

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

        for (int i = 0; i < m; i++) {
            outNum[i] = Integer.parseInt(st.nextToken());
        }

        Deque<Integer> dequeue = new ArrayDeque<>();

        for (int i = 0; i < num; i++) {
            dequeue.offerLast(i + 1);
        }
        for (int target : outNum) {
            int idx = indexDequeue(dequeue, target);

            if (target == dequeue.peek()) {
                dequeue.pollFirst();
            } else {
                if (idx > dequeue.size() / 2) {
                    // rightshift
                    while (dequeue.peek() != target) {
                        rightShiftQueue(dequeue);
                        answer++;
                    }
                    dequeue.pollFirst();
                } else {
                    // leftshift
                    while(dequeue.peek() != target) {
                        leftShiftQueue(dequeue);
                        answer++;
                    }
                    dequeue.pollFirst();
                }
            }

        }
        System.out.print(answer);
    }

    public static void leftShiftQueue(Deque<Integer> dequeue) {

        int tmp = dequeue.pollFirst();
        dequeue.offerLast(tmp);
    }
    public static void rightShiftQueue(Deque<Integer> dequeue) {

        int tmp = dequeue.pollLast();
        dequeue.offerFirst(tmp);
    }
    public static int indexDequeue(Deque<Integer> dequeue, int target) {
        Deque<Integer> tmp = new ArrayDeque<>(dequeue);
        int idx = 0;
        while (tmp.pollFirst() != target) {
            idx++;
        }
        return idx;
    }
}