[BOJ] 백준 1021 - 회전하는 큐 풀이

1. 문제

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

1021번: 회전하는 큐

 

2. 풀이

백준 실버 3에 해당하는 문제이고, 문제 자체를 처음에 잘못 접근해서 시간을 많이 날린 문제다....

처음 생각해낸 접근 방식은 주어지는 N과 M의 크기가 작아서 재귀를 통한 완전 탐색으로 문제를 해결하려 했다.
물론 이 방식으로는 해결하지 못했다... (혹시 재귀로 해결하신분이 있다면 댓글로 링크나 풀이 방식을 공유해주십쇼 꾸벅 ㅠㅠ)

두 번째 방식으로 이분 탐색에서 힌트를 얻었다. 
이분 탐색은 원소의 처음과 끝을 더하여 반을 나눈 위치에서 인덱스를 더하고 빼서 내가 원하는 위치를 찾는 알고리즘이다.
이 과정에서 힌트를 얻어서 현재 존재하는 리스트의 총 길이의 반보다 내가 찾으려는 원소의 인덱스가 작다면 왼쪽으로 Shift, 크다면 오른쪽으로 Shift 하는 것이다. (이 방법을 생각하면 문제는 정말 간단해진다.)

32번째 줄부터 원하는 수를 탐색하기 시작한다.
Check() 함수를 통해 내가 현재 찾으려는 수의 위치가 현재 리스트의 길이의 반보다 작다면 찾을 때 까지 왼쪽으로 Shift, 크다면 찾을 때까지 오른쪽으로 Shift를 한다. Shift할 때마다 cnt의 값을 +1 해준다. 이러면 왼쪽, 오른쪽을 다 탐색하면서 최솟값을 찾지 않아도 자동으로 최솟값으로 결과가 나온다.

마지막으로 cnt의 값을 출력하면 정답!!!

 

3. 소스 코드

import java.io.*;
import java.util.*;

public class Main {

    static int N, M;
    static int cnt = 0;

    static LinkedList<Integer> queue;
    static List<Integer> SelectedWant;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            queue.offer(i + 1);
        }

        SelectedWant = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            SelectedWant.add(Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < M; i++) {
            if (Check(SelectedWant.get(i))) {  // 찾으려는 위치가 큐 크기 절반보다 작다면 왼쪽으로 이동
                while (queue.get(0) != SelectedWant.get(i)) {
                    queue.addLast(queue.pollFirst());
                    cnt += 1;
                }

            } else {                // 찾으려는 위치가 큐 크기 절반보다 크다면 오른쪽으로 이동
                while (queue.get(0) != SelectedWant.get(i)) {
                    queue.addFirst(queue.pollLast());
                    cnt += 1;
                }
            }

            queue.poll();
        }

        bw.write(Integer.toString(cnt));
        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean Check(int peeked) {
        for (int i = 0; i <= queue.size() / 2; i++) {
            if (peeked == queue.get(i)) {
                return true;
            }
        }

        return false;
    }
}