Problem Solve

[백준 / BOJ] 1021 : 회전하는 큐 (JAVA)

black6765 2023. 1. 7. 23:18

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

 

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

  1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
  2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
  3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

전체 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int M = Integer.parseInt(s[1]);

        String[] input = br.readLine().split(" ");

        LinkedList<Integer> list = new LinkedList<>();

        for (int i = 1; i <= N; i++) {
            list.add(i);
        }

        int ans = 0;
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(input[i]);

            if (list.peekFirst() == target) {
                one(list);
            } else {
                int idx = list.indexOf(target);

                if (idx <= Math.ceil(list.size() / 2)) {
                    while (true) {
                        two(list);
                        ans++;
                        if (list.peekFirst() == target) {
                            one(list);
                            break;
                        }
                    }

                } else {
                    while (true) {
                        three(list);
                        ans++;
                        if (list.peekFirst() == target) {
                            one(list);
                            break;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }

    public static <T> void one(LinkedList<T> list) {
        list.removeFirst();
    }

    public static <T> void two(LinkedList<T> list) {
        list.addLast(list.removeFirst());
    }

    public static <T> void three(LinkedList<T> list) {
        list.addFirst(list.removeLast());
    }
}

 

풀이

간단해보이는 문제였으나, 예상보다 생각할 거리가 있는 문제였다.

 

우선 문제의 요구사항에 따라 3개의 연산을 메소드로 만들었다.

그리고 입력에 대한 처리를 한 후 알고리즘을 고민하였다.

 

문제 조건에서의 큐는 원형 큐의 형태로 볼 수 있으며, 2번째 연산 또는 3번째 연산 중 어느 것을 해야 하는지는 현재 리스트의 크기를 2로 나눈 값을 소수점 첫째 자리에서 올림한 값( idx <= Math.ceil(list.size() / 2) )에 따라 다르다.

 

만약 리스트의 크기가 5라면, 이를 2로 나눈 결과를 올림한 값은 3이 된다. 따라서 꺼내려고 하는 값의 인덱스 범위가 1 ~ 3이라면 two 연산을, 그 외의 범위라면 three 연산을 원하는 값이 첫번째 인덱스로 올 때까지 하는 것이 최소 횟수로 해결 가능한 방법이다. 이는 while (true) 문에서 peek 메소드를 이용해 조건을 확인하고, 해당될 때까지 반복한 후 break 하는 식으로 구현하였다.

 

느낀점

이러한 알고리즘을 유추하기 위해서 머리 속으로 문제의 테스트 입출력을 직접 돌려보면서, 어떤 인덱스 범위에서 어느 연산을 수행해야 하는지 고민해보는 것이 문제 난이도에 비해 많은 시간을 투자하게 한 것 같다.

 

또한 올림 함수 Math.ceil() 메소드를 사용해본지가 오래 되었는데, 반올림 함수인 round, 버림 함수인 floor 등과 같이 학습해보는 기회가 되었다. 특히 특정 자릿수에서 올림/반올림/버림 하기 위해서 Math.ceil( 값 * 10^(표현할 소수점 자릿수) / 10^(표현할 소수점 자릿수) )와 같은 테크닉도 다시 인식하게 되었다.

 

저작자표시