[백준] 1021번 회전하는 큐 _ JAVA ( 주석 설명 )

풀이

1) 뽑아내려고 하는 수(num)를 기준으로 왼쪽이 더 많은지, 해당 수를 포함해서 오른쪽이 더 많은지 비교해야 한다. => Deque 사용


2) num이 나올 때까지 pollFirst(), pollLast()를 실행한다. 연산 count++


3) poll을 통해 추출한 수가 num과 같으면 이전까지 poll 했던 것들을 원상복귀를 시킨다. (deque.addAll())

 	- pollLast()가 같을 시에는 1번째 인덱스로 이동하는 과정이 필요하므로 count++
   
   
3) 계산한 연산 수 count를 출력한다.



+
LinkedList로 deque을 만들어

deque.indexOf(num)을 이용해 찾고자 하는 num의 인덱스를 찾고

해당 인덱스와 중간 인덱스를 비교하여

왼쪽 이동, 오른쪽 이동을 결정할 수 있다.
+

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
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());

        ArrayDeque<Integer> deque = new ArrayDeque<>();
        //deque에 1~N까지 원소 넣기
        for(int i=1;i<=N;++i){
            deque.addLast(i);
        }


        int count = 0; //왼쪽과 오른쪽으로 움직이는 연산 횟수를 센다.
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;++i){
            int num = Integer.parseInt(st.nextToken()); //뽑아내려고 하는 숫자

            ArrayDeque<Integer> first_deque = new ArrayDeque<>();
            ArrayDeque<Integer> end_deque = new ArrayDeque<>();
            while(true){
                Integer first = deque.pollFirst(); //deque에서 맨 첫번째 원소를 추출한다.
                if(first != null) //남아 있는 원소가 홀수개 남아있으면 null 이 될 수 있다.
                    first_deque.addLast(first); //첫번째 원소들을 모아둔다. //왼쪽부터, 원래 deque 뒤에 붙일 용도

                Integer end = deque.pollLast(); //deque에서 마지막 원소를 추출한다.
                if(end != null)
                    end_deque.addFirst(end); //마지막 원소들을 모아둔다. //오른쪽부터, 원래 deque 앞에 붙일 용도


                if(first==num){ //만약 첫번째 원소가 같다면
                    first_deque.pollLast(); //first_deque에서 같은 원소를 제한다.
                    deque.addAll(end_deque); //마지막 원소 poll 했던 것들을 원상복귀한다. deque + 마지막 원소들
                    deque.addAll(first_deque); //그 전까지 첫번째 원소들을 모아둔 first_deque을, 원래 deque 뒤에 이어 붙인다.
                    break;
                }

                else if(end==num) { //마지막 원소가 같다면
                    count++; //마지막 원소를 앞으로 이동하는 과정을 카운팅한다.
                    end_deque.pollFirst(); //end_deque에서 같은 원소를 제한다.
                    first_deque.addAll(deque);//첫번째 원소 poll 했던 것들을 원상복귀한다. 첫번째 원소들 + deque
                    deque = first_deque;
                    end_deque.addAll(deque); //그 전까지 마지막 원소들을 모아둔 end_deque을, 원래 deque 앞에 이어 붙인다.
                    deque = end_deque;
                    break;
                }

                //첫번째 or 마지막 원소 모두 입력받은 num과 다르다면
                //양방향 어느쪽으로든 이동을 해야 하므로 해당 이동 횟수를 count 해준다.
                count++;
            }
        }
        System.out.println(count);
    }
}