1021번

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

1021번: 회전하는 큐

오늘 풀은 문제는 덱큐 문제인데, 좀 시간이 걸렸다.

이 문제에서 주의 할 것은 값을 빼는 것은 무조건 첫번째 인덱스라는 것이다.

나는 첫번째와 마지막에서 둘다 뺄 수 있는 줄 알고 로직을 짰다가 고생을 했다..

 

동작 방식은 간단하다.

주어진 뽑으려는 위치에 있는 값을 저장하고, 앞과 뒤중에 그 값에 더 가까운 곳에서 시작해서 뽑은 값을 옮기면 된다.

뽑으려는 값의 인덱스 위치를 찾고, 전체 큐의 크기에서 인덱스 값을 뺏을 때, 인덱스 값이 전체 큐의 크기에서 인덱스 값을 뺀 값보다 작다면

앞에서부터 값을 빼서 뒤로 옮기는 방식으로 찾으려는 값을 찾고, 찾는 과정에서 옮긴 횟수를 증가 시키면서 저장한다.

예를 들어 3 3 \n 2 1 3 이면 1 2 3 -> 2 3 1로 바꾸고 cnt+1, 2를 뽑고, 3 1 -> 1 3로 바꾸고 cnt+1하고 1뽑고, 3뽑는다.

그러면 횟수는 2이다.

 

정답 코드는 아래와 같다. 

package backjoon.b1021;

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

public class b1021 {
    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());

        LinkedList<Integer> deque = new LinkedList<>();
        int[] find = new int[M];
        
        st=new StringTokenizer(br.readLine());

        for(int i=0; i<M; i++){
            find[i]= Integer.parseInt(st.nextToken());
        }//찾아야할 인덱스값

        for(int i=1; i<=N; i++){
            deque.add(i);
        }//큐 채우기
        int count=0;
        for(int i=0; i<M; i++){
//            int target = deque.indexOf(find[i]);
//            int half;
//            if(deque.size()%2==0){
//                half = deque.size()/2-1;
//            }
//            else {
//                half = deque.size()/2;
//            }

//            if(target<=half){
            int comp = deque.indexOf(find[i]);

            if(deque.size()-comp>=comp){
                    while (true){
                        int tmp = deque.pollFirst();

                        if(tmp==find[i]){
                            break;
                        }
                        deque.addLast(tmp);
                        count++;
                    }
            }
            else {
                    while (true){
                        int tmp = deque.pollLast();

                        if(tmp==find[i]){
                            count++;
                            break;
                        }
                        deque.addFirst(tmp);
                        count++;
                    }
                }
            }

        System.out.println(count);

    }
}