BOJ_1021_회전 하는 큐 JAVA 풀이

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

해당 문제는 JAVA에서 잘 구현된 자료구조를 이용하여, 해당 원소의 현재 위치가 어디있는지 찾은 후,

해당 원소의 위치가 원소 배열의 중간보다 작다면, 왼쪽으로 한 칸 이동 연산을 반복적으로 수행하며
원소 배열의 중간보다 크다면, 오른쪽으로 한 칸 이동 연산을 반복적으로 수행한다.
해당 원소가 뽑을 수 있는 위치에 왔을 때까지 연산을 반복한다.

// 위치 찾아서 처음, 중간 비교
if (idx <= deque.size() / 2){
	while (!deque.isEmpty() && toFindE != deque.peek()){
    	deque.offerLast(deque.pollFirst());
        answer++;
    }
}else {
	while (!deque.isEmpty() && toFindE != deque.peek()){
    	deque.offerFirst(deque.pollLast());
        answer++;
	}
}
deque.poll();

해당 문제의 자료구조 개념은 양 끝에 모두 검색, 삽입, 삭제가 가능한 Deque(덱)을 이용하며,

자바 컬렉션을 상속받은 interface인 Deque를 이용한다.

해당 자료구조의 상속 개념도를 간략하게 나타낸다면,

이며 자세한 구조를 알고 싶다면
https://docs.oracle.com/javase/8/docs/api/
자바 document를 참조하기 바란다.

통과 코드

import java.util.*;
import java.util.Deque;

public class BOJ_1021_회전하는큐 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < m; i++){
            queue.offer(sc.nextInt());
        }

        System.out.println(new BOJ_1021_회전하는큐().solution(n, m, queue));

    }

    private int solution(int n, int m, Queue<Integer> queue) {
        int answer = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 1; i <= n; i++){
            deque.offer(i);
        }

        while (!queue.isEmpty()){
            int toFindE = queue.poll();
            int idx = 0;
            for (int e : deque){
                if (e == toFindE) break;
                idx++;
            }

            // 위치 찾아서 처음, 중간 비교

            if (idx <= deque.size() / 2){
                while (!deque.isEmpty() && toFindE != deque.peek()){
                    deque.offerLast(deque.pollFirst());
                    answer++;
                }
            }else {
                while (!deque.isEmpty() && toFindE != deque.peek()){
                    deque.offerFirst(deque.pollLast());
                    answer++;
                }
            }
            deque.poll();
        }


        return answer;
    }
}