BackJoon 1021, 회전하는 큐

BackJoon 1021, 회전하는 큐 - deque 문제

이번 문제는 덱(deque)를 사용하는 문제를 가지고 왔습니다.

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

이 문제는 생각하기가 어려웠던 문제입니다.

환형 큐를 돌리면서 최소한으로 움직여서 원하는 값들을 빼내는 문제입니다.

제가 실수 했던 부분이 deque의 특성 상, 앞과 뒤 모두 polling을 할 수 있습니다.

그래서 출구가 2개라고 생각하고 데이터를 뺐습니다. 하지만 이 문제에서는 출구가 하나라고 생각하고 풀어내야하죠.

그리고 큐를 돌리는 방향도 생각을 해야하지만, 저는 무조건 왼쪽으로만 돌리고

큐 사이즈의 반보다 크면 사이즈에서 지금까지 회전한 횟수를 빼는 형식으로 구했습니다.

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

public class B1021 {
    static int N, M, count = 0, first;
    static String in, ins[];
    static ArrayList<Integer> numbers = new ArrayList<>();
    static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        in = br.readLine();
        N = Integer.parseInt(in.split(" ")[0]);
        M = Integer.parseInt(in.split(" ")[1]);
        ins = br.readLine().split(" ");
        for (int i = 0; i < M; i++) {
            numbers.add(Integer.parseInt(ins[i]));
        }
        for (int i = 1; i <= N; i++) {
            list.add(i);
        }
        boolean isPoll = true;
        int ans = 0;
        while (!numbers.isEmpty()) {
            if (isPoll) {
                count = 0;
                first = list.get(0);
            }
            if (numbers.get(0).equals(list.get(0))) {
                list.remove(0);numbers.remove(0);
                ans += (count > list.size() / 2) ? list.size() - count + 1 : count;
                isPoll = true;
            }else {
                leftRotate();count++;
                isPoll = false;
            }
        }
        bw.write(ans + "\n");
        bw.flush();bw.close();

    }
    public static void leftRotate() {
        int t = list.remove(0);
        list.add(t);
    }
}

이 블로그 검색

Do.

BackJoon 1021, 회전하는 큐 - deque 문제

이 블로그의 인기 게시물

웹툰 무료로 볼 수 있는 사이트

BackJoon 1011, Fly me to the alpha centauri, 규칙 찾기 문제

BaekJoon 14501, 퇴사 dp or dfs