[백준] 1021번 - 회전하는 큐

💎 문제 링크

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

1021번: 회전하는 큐

 

📝 문제

 

✍🏻 입력 & 출력

 

🤔 풀기 전에 생각하기

문제를 이해하기 위해 예제 입력에 따른 출력이 어떤 과정을 통해 나왔는지 먼저 생각한다.

1번 연산은 맨 앞에있는 숫자만 뽑는 연산이기 때문에 필요한 숫자를 맨 앞으로 보내야한다.

 

✔️ 예제 입력 1

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 중에서 3개의 숫자 [1, 2, 3]을 뽑아냄[1, 2, 3]은 앞에서 부터 차례대로 뽑아내는 연산인 1번 연산만 3번 하면 해결

 

2번, 3번 연산은 필요없기 때문에 결과값은 0

 

✔️ 예제 입력 2

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 중에서 3개의 숫자 [2, 9, 5]를 뽑아냄

 

2를 뽑기 위해선 2번 연산 한 번으로 1을 맨뒤로 보낸 뒤 맨 앞으로 온 2를 뽑음

Queue : [3, 4, 5, 6, 7, 8, 9, 10, 1]

remain : [9, 5]

count   : 1

 

9를 뽑는 과정은 3번 연산을 세 번 [9, 10, 1, 3, 4, 5, 6, 7, 8] 한 뒤 9 추출

Queue : [10, 1, 3, 4, 5, 6, 7, 8]

remain : [5]

count   : 4

 

5는 3번 연산을 네 번 [5, 6, 7, 8, 10, 1, 3, 4] 한 뒤에 추출

Queue : [6, 7, 8, 10, 1, 3, 4]

remain : []

count   : 8

 

결과값은 8

 

✨ 풀이

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        LinkedList<Integer> queue = new LinkedList<>();
        /*
         * Queue Interface 에는 
         * offerLast(), offerFirst(), pollFirst(), pollLast()
         * 메소드가 없기 때문에
         * LinkedList 로 생성
         */
        
        int queueSize = scanner.nextInt(); // 큐의 크기
        int needNum = scanner.nextInt();   // 필요한 숫자 개수
        int[] numbers = new int[needNum];  // 필요한 숫자들
        int count = 0;  // 연산 횟수

        // 필요한 숫자들 입력
        for (int i = 0; i < needNum; i++) {
            numbers[i] = scanner.nextInt();
        }

        // 큐 초기화
        for (int i = 1; i <= queueSize; i++) {
            queue.offer(i); // 예외 발생 없이 false, true 리턴하는 offer() 사용
        }

        for (int i = 0; i < needNum; i++) {
            int numIndex = queue.indexOf(numbers[i]); // 최소값을 구하기 위해 어디 위치하는지 저장
            int middleIndex = (queue.size() % 2 == 0) ? (queue.size() / 2 - 1) : (queue.size() / 2); // 가운데를 기준으로 양쪽을 봐야하기 때문에 위치 저장

            if (numIndex <= middleIndex) { // 찾는 숫자가 중간보다 앞이면
                for (int j = 0; j < numIndex; j++) { // 그 수의 인덱스까지만 체크하기 때문에 peek으로 비교하는 과정은 필요없음
                    queue.offerLast(queue.pollFirst()); // 원소가 앞쪽에 있으면 앞에서 꺼내서 뒤에서 추가
                    count++; // 2번 연산 count
                }
            } else {
                for (int j = 0; j < queue.size() - numIndex; j++) {
                    queue.offerFirst(queue.pollLast()); // 원소가 뒤쪽에 있으면 뒤에서 꺼내서 앞으로 추가
                    count++; // 3번 연산 count
                }
            }
            queue.pollFirst(); // 2번 3번 연산이 끝나면 원하는 원소가 맨 앞으로 온 것. 바로 poll 수행

        }

        System.out.println(count);

    }
}