[java 백준] 1021 - 회전하는 큐

1021번: 회전하는 큐

---

LinkedList 를 통해 구현하였다

전체 범위의 숫자를 LinkedList에 담아두고 뽑아야 하는 숫자를 만나면 삭제하는 방식으로 구현했다

뽑아야 하는 숫자를 int[] 에 담고
int[] 에 들어있는 숫자를 다 뽑을때 까지 while문을 수행한다.

 

while문에서 list의 맨 앞 숫자를 뽑아서 

해당 숫자와 int[] 의 첫번째 숫자와 비교한다.

 

만약 다른 숫자라면 LinkedList를 오른쪽 혹은 왼쪽으로 옮긴다

1 2 3 4 5 -> 2 3 4 5 1 (왼쪽으로 이동 시)

 

최단거리로 옮기기 위해 방향을 구하는 방법은

linkedList에서 뽑아야 하는 숫자의 위치와 

linkedList의 크기를 2로 나눈 수를 비교하여 

더 가까운 방향으로 int[] 안의 수와 만날 때 까지 linkedList를 움직인다. 

 

---

package com.exam.자료구조;
// 회전하는 큐
// https://www.acmicpc.net/problem/1021

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B1021 {
    static int N,M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st =  new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int[] index = new int[M];
        st =  new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            index[i] = Integer.parseInt(st.nextToken());
        }
        LinkedList<Integer> d = new LinkedList<>();
        for (int i = 1; i < N+1; i++) {
            d.add(i);
        }

        int count =0;
        int move = 0;
        while(true){
            if(count>=M) {
                break;
            }else if(d.getFirst() == index[count]) {
                d.removeFirst();
                count++;
            }else{
                int idx = d.indexOf(index[count]);
                int size = d.size()/2;
                if(idx>size) {
                    while(true){
                        if(d.getFirst() == index[count]) break;
                        else {
                            // 리스트를 옮기기 위해
                            // 마지막 숫자를 temp에 저장 후 
                            // 마지막 숫자를 삭제하고
                            // (저장해둔 숫자)temp를 첫번째에 삽입한다
                            int temp = d.getLast();
                            d.removeLast();
                            d.addFirst(temp);
                            move++;
                        }
                    }
                }else{
                    while(true) {
                        if(d.getFirst() == index[count]) break;
                        else {
                            // 리스트를 옮기기 위해
                            // 첫번째 숫자를 temp에 저장 후 
                            // 첫번째 숫자를 삭제하고
                            // (저장해둔 숫자)temp를 마지막에 삽입한다
                            int temp = d.getFirst();
                            d.removeFirst();
                            d.addLast(temp);
                            move++;
                        }
                    }
                }
            }
        }
        System.out.println(move);
    }

}