[백준 2024/01/18] 1021번 회전하는 큐

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

1021번: 회전하는 큐

 

1. 접근 방법

이번 문제는 왼쪽으로 돌려서 원하는 수를 찾을 것인지,

오른쪽으로 돌려서 원하는 수를 찾을 것인지가 쟁점인 문제였다.

 

더불어서, 1) pop을 하는 방식은 원하는 원소를 뽑아내려고 할 때만 사용이 될 것이라, 하나의 부품으로 보고 접근하였다.

 

rough draft

 

방향을 결정하는 방법으로, 원하는 값의 위치가 길이/2을 기준으로 왼쪽에 있느냐 오른쪽이 있느냐 였다.

~~~~?~~ | ~~~~~~

찾고자하는 값, ? 가 길이를 절반으로 나누었을 때, 왼쪽에 있다면 오른쪽으로 돌려서 해당 값이 첫 번째로 오도록 하는 것이 편할 것이다.

그 반대의 경우는 왼쪽으로 돌려서 값이 첫 번째로 오도록 하는 것이 편할 것이다.

 

따라서, 이를 기준으로 if-else문으로 나누어,

deque.removeFirst()를 할 것인지,

deque.removeLast() 를 할 것인지 결정해주었다.

 

2. 코드

import java.util.Objects;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Scanner;

public class b1021 {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] numbs = line.split("\\s+");

        Deque<Integer> deque = new ArrayDeque<>();

        for(int i = 1; i<=Integer.parseInt(numbs[0]); i++){
            deque.addLast(i);
        }

        String num_want = scanner.nextLine();
        String[] num_w = num_want.split("\\s+");
        int move = 0;
        for (int i=0; i<Integer.parseInt(numbs[1]);i++){
            int num_integer = Integer.parseInt(num_w[i]);
            int index = 1;

            for(int current:deque){
                if(Objects.equals(current, num_integer)){
                    break;
                }
                else{
                    index++;
                }
            }

            if(deque.size()/2+1>=index){
                while(!Objects.equals(deque.peekFirst(),num_integer)){
                    int add_last = deque.removeFirst();
                    deque.addLast(add_last);
                    move +=1;
                    //System.out.println("first");
                }
                deque.removeFirst();
            }
            else{
                while(!Objects.equals(deque.peekFirst(),num_integer)){
                    int add_first = deque.removeLast();
                    deque.addFirst(add_first);
                    move+=1;
                    //System.out.println("second");
                }
                deque.removeFirst();
            }
            //System.out.println("----------");

        }
        System.out.println(move);

    }

}