[백준 1021번][Java][Deque] 회전하는 큐

문제

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

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

• 첫 번째 원소를 뽑아낸다.
• 왼쪽으로 한 칸 이동시킨다.
• 오른쪽으로 한 칸 이동시킨다.

 

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

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

내 풀이

• 처음에는 일반적인 queue로 접근했으나 3번 연산에 막혀 구글링 후 deque라는 것이 있다는 것을 알게됨.
• 이후 deque의 앞뒤로 추가/삭제 할 수 있는 성질을 이용해 풀이 완료
• target의 index를 얻기 위해 메소드를 사용하고 싶었지만 아쉽게도 deque는 index를 바로 얻을 수 없었다. 따라서 deque를 돌면서 target과 같은 값을 만날 때 까지 index를 증가 시키는 for문을 이용해 index를 구했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> deque = new LinkedList<>();
        int count = 0;

        // get N, M
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // get element's location
        int[] location = new int[m];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            location[i] = Integer.parseInt(st2.nextToken());
        }

        // create queue
        IntStream.range(1, n + 1).forEach(x -> deque.add(x));

        for (int target : location) {
            int index = 0;

            for (int x : deque) {
                if (x == target) { // get target's index
                    break;
                }
                index++;
            }

            if (index <= deque.size() - index) {
                while (deque.peekFirst() != target) {
                    deque.addLast(deque.pollFirst());
                    count++;
                }
            } else {
                while (deque.peekFirst() != target) {
                    deque.addFirst(deque.pollLast());
                    count++;
                }
            }
            deque.pollFirst();
        }
        System.out.println(count);
    }
}