[Java][백준 1021번] : 회전하는 큐

 

[ 목차 ]

---

📢 문제 출처

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

1021번: 회전하는 큐

---

⏰ 문제 설명

---

⏰ 입출력 예시

---

⏰ 문제 풀이 정리 (feat. 문제이해를 제대로 못해서 그림으로 정리)

 

---

⏰ 풀이

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SpinningQueue {
    public static void main(String[] args) {

        //입력
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();   //크기
        int m = sc.nextInt();   //갯수

        LinkedList queue = new LinkedList();
//        Queue queue = new LinkedList();
        for (int i = 0; i < n; i++) {
            queue.add(i + 1);
        }

        int count = 0;

        //움직일 때 최소값으로 이동해야한다!!!
        //ex. 왼쪽이 2이고, 오른쪽이 3이면, 2로 이동해야한다.
        for (int i = 0; i < m; i++) {
            int num = sc.nextInt();

            int index = queue.indexOf(num); //시스템에 적은 값의 인덱스 위치 확인
            int half_size = queue.size()/2; //중간을 기준으로 어느 방향으로 갈지 확인

            //사용자가 넣은 값이 리스트의 첫번째 위치가 아니면
            while(num != (int)queue.getFirst())
            {
                //중간보다 작으면(왼쪽으로)
                if(index <= half_size){
                    queue.add(queue.removeFirst()); //queue.removeFirst() 위치에 더해라
                }
                //중간보다 크면(오른쪽으로)
                else{
                    queue.addFirst(queue.removeLast());  //queue.removeLast() 위치에 더해라
                }
                count++;
            }
            queue.removeFirst();    //옮긴 다음에는 옮긴 숫자(첫번째 위치의 값)를 지워라.
        }
        System.out.println(count);
    }
}

✔ Queue queue 대신에 LinkedList 사용한 이유

 -. Queue로 오만가지 대입을 해보다가 정 안되서. queue를 생성할 때 LinkedList를 사용하기에 변경 진행해봤다.

✔ LinkedList의 속성

-. 내부적으로 양방향의 연결리스트로, 참조하려는 원소에 따라서 순방향, 역방향으로 순회 가능하다.

-. Queue의 속성인 "선입선출"도 LinkedList를 이용하면 사용이 가능하다는 것이다.

-. Queue로 진행했을 때 막히면, LinkedList로 선언해서 Queue처럼 사용하면 괜찮은 방안인 거 같다.

서로 구현 가능한 자료형