[백준] 1021: 회전하는 큐

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int count = 0;
    static LinkedList<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int[] temp = new int[M];
        for (int i = 0; i < M; i++)
            temp[i] = Integer.parseInt(st.nextToken());

        // 큐 초기화
        for (int i = 1; i <= N; i++)
            q.add(i);

        // 뽑아내기 작업 수행
        for (int i = 0; i < M; i++) {

            // 목표 원소가 큐의 왼쪽에 위치하면 true, 오른쪽에 위치하면 false
            if (check(temp[i])) {
                while (temp[i] != q.get(0)) {
                    q.addLast(q.pollFirst());
                    count++;
                }
            } else {
                while (temp[i] != q.get(0)) {
                    q.addFirst(q.pollLast());
                    count++;
                }
            }

            // 뽑아낸 원소 제거
            q.poll();
        }

        // 최종 결과 출력
        System.out.println(count);
    }

    // 현재 큐에서 특정 원소의 위치 확인
    public static boolean check(int a) {
        for (int i = 0; i <= q.size() / 2; i++) {
            if (a == q.get(i))
                return true;
        }
        return false;
    }
}

 

 

이 코드는 양방향 순환 큐에서 여러 원소를 뽑아내는 작업을 수행한다.

 

주어진 크기 N의 큐에 대해 여러 원소를 뽑아내는데 필요한 최소한의 이동 횟수를 계산한다.

 

주요 포인트

1. LinkedList<Integer> q를 이용하여 양방향 순환 큐를 구현한다.
2. check 메서드는 현재 큐에서 특정 원소의 위치를 확인하는 역할을 한다. 큐의 크기의 절반을 기준으로 원소를 찾아내는데, 만약 찾는 원소가 큐의 왼쪽 절반에 위치한다면 true를 반환하고 오른쪽 절반이면 false를 반환한다.
3. 뽑아내려는 각 원소에 대해 목표 원소의 위치에 따라 왼쪽 또는 오른쪽으로 이동시키면서 필요한 이동 횟수를 계산한다. 뽑아내고 나면 count에 이동 횟수를 누적하고 해당 원소를 큐에서 뽑아낸다.

 

코드 설명

• q를 이용하여 큐를 초기화하고 뽑아내려는 원소의 위치에 따라 왼쪽 또는 오른쪽으로 이동시키면서 이동 횟수를 계산한다.
• check 메서드를 통해 현재 큐에서 원소의 위치를 확인하여 어느 쪽으로 이동해야 하는지 판단한다.
• 주어진 목표 원소에 대해 이동이 완료되면 해당 원소를 큐에서 뽑아낸다.
• 모든 뽑아내기 작업이 끝나면 count를 출력하여 최종 결과를 표시한다.