[BOJ] 1021 - 회전하는 큐 (JAVA)

문제출처 : 링크텍스트

---

문제 요약 설명

주어진 양방향 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

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

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

---

풀이방법

회전초밥이 먹고싶습니다. 요즘 일본에는 회전초밥에 테러를 하는 쓰레기들이 있다고 하는데 부디 한국에는 그런 문화가 옮지 않기를 바랍니다.

이 문제의 핵심은 뽑아내려는 숫자의 위치에 indexOf() 메서드를 통하여 접근하고, indexOf()를 통해서 알아낸 위치는 왼쪽으로 회전하여 그 숫자를 뽑아내는 데 드는 비용이고, q의 크기에서 이를 빼면 오른쪽으로 회전하여 뽑아드는데 드는 비용임을 상기하여야 한다는 점입니다.
아, 하나 더!! 양방향 순환 큐를 이용하여야 하기 때문에 HEAD가 존재하지 않는 콜렉션 Queue<>()는 사용하여서는 안됩니다.

• 입력을 받고, LinkedList<>()를 준비합니다.
  - Queue<>() 콜렉션으로 구현할 경우, HEAD가 존재하지 않아 맨 앞의 원소에 접근할 수 없기 때문입니다.
• 뽑아내려는 원소의 위치가 담긴 배열 int[] seq를 순회하며 큐를 회전시켜 숫자를 뽑아냅니다.
  - 이 때, 뽑아내려는 원소의 위치는 처음 큐에서의 위치이므로, 큐가 자기자신의 처음 위치를 값으로 가지도록 하면 구현이 쉽습니다.
  - 뽑아내려는 숫자의 위치에 indexOf() 메서드를 통하여 접근합니다. indexOf()를 통해서 알아낸 위치는 왼쪽으로 회전하여 그 숫자를 뽑아내는 데 드는 비용이고, q의 크기에서 이를 빼면 오른쪽으로 회전하여 뽑아드는데 드는 비용입니다.

---

문제풀이

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

public class BOJ1021_회전하는큐 implements Application {
    static Scanner sc = new Scanner(System.in);
    static LinkedList<Integer> q; // Queue<Integer> q=new LinkedList<>() 와  Queue<Integer> q=new Queue<>(), 그리고 LinkedList<> q=new LinkedList<>(); 의 차이점?
    static int[] seq;
    static int countOp2 = 0;
    static int countOp3 = 0;

    public static void main(String[] args) {
        // N,M 입력 받아서 저장
        int[] NM = Arrays.stream(sc.nextLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int N = NM[0];
        // 시작위치를 자기 값으로 가진 양방향 큐 생성
        q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            q.add(i + 1);
        }
        // 뽑아내려는 수의 위치를 입력받아 IntStream으로 기록
        seq = Arrays.stream(sc.nextLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        // 연산 시작
        int j=0;
        while(j<seq.length){
            int idxNumber=seq[j];
            if(!q.isEmpty()) {
                if (q.peek() == idxNumber) { // 뽑고자 하는 위치와 현재 HEAD가 같으면
                    operation1st();
                    j++;            // 다음 순서의 뽑고자 하는 숫자로 이동
                } else {            // 뽑고자 하는 위치와 현재 HEAD가 다르면
                    if (q.indexOf(idxNumber)>q.size()-q.indexOf(idxNumber)) {  // 왼쪽으로 움직여 빼는 횟수보다 오른쪽으로 움직여 빼는 횟수가 적으면
                        operation3rd();
                    } else {
                        operation2nd();
                    }
                }
            }
        }
        System.out.println(countOp2+countOp3);
    }

    static private void operation1st() {
        q.poll();
    }

    static private void operation2nd() {
        q.add(q.poll());
        countOp2++;
    }

    static private void operation3rd() {
        q.addFirst(q.pollLast());
        countOp3++;
    }
}

---