백준 1021번 회전하는 큐 제로베이스 자료구조 2일차 주체 : Queue

자료구조 1 Page 노트 정리 2일차 주제 : Queue

 

 

백준 1021번 회전하는 큐 문제풀이

백준 1021번 문제

 

2번, 3번 연산을 수행하기 위해서는 뽑아야 하는 값이 Queue Front에서 오른쪽으로 이동하는 것이 가까운지 왼쪽으로 이동하는 것이 가까운지 찾아야 하는 작업을 진행해야 한다.

이 작업을 진행하기 위해서 Queue의 사이즈를 2로 나눠서 그 값 보다 뽑아야 하는 값이 크다면 오른쪽으로 이동시키고,

작다면 왼쪽으로 이동시켜서 문제를 풀었다.

 

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // 2번 3번 연산의 최솟값을 구할 변수
        int count = 0;

        Scanner sc = new Scanner(System.in);
        LinkedList<Integer> queue = new LinkedList<>();

        // N 과 M을 입력받아 공백(" ")으로 split해서 String 배열에 담기
        String[] inNM = sc.nextLine().split(" ");
        // 뽑아내려고 하는 수의 위치를 배열로 담기 위해 공백(" ")으로 split 진행하고
        // stream의 mapToInt를 이용해 String에서 int형으로 변환후 배열로 만듦
        int[] position = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int n = Integer.parseInt(inNM[0]);
        int m = Integer.parseInt(inNM[1]);

        // N개 만큼 queue 생성
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }

        for (int i = 0; i < m; i++) {
            // 뽑아내려고 하는 수의 위치
            int targetNum = queue.indexOf(position[i]);

            if (targetNum > (queue.size() / 2)) {
                // queue를 오른쪽으로 회전
                while (position[i] != queue.getFirst()) {
                    queue.addFirst(queue.removeLast());
                    count++;
                }
            } else {
                // queue를 왼쪽으로 회전
                while (position[i] != queue.getFirst()) {
                    queue.addLast(queue.removeFirst());
                    count++;
                }
            }
            
            queue.removeFirst();
        }

        System.out.println(count);
    }
}