[백준] 1021 회전하는 큐 - Data Structure / Java

• 문제 링크

1021번: 회전하는 큐

 

• 풀이 과정

Deque 자료구조를 활용하여 회전하는 큐를 구현한다.

큐의 크기 n을 입력받은 후 덱에 1 ~ n 의 범위의 정수를  offer 하고, 뽑아낼 원소  m개를 차례로 입력받는다.

 

향상된 for 문을 활용하여 추출할 원소의 인덱스를 구하고,

해당 인덱스가 0 일 경우 pollFirst 하여 덱의 첫번째 원소를 추출하며

 

그렇지 않을 경우 해당 인덱스가 덱의 중앙(dq.size() / 2) 에서 어느쪽에 가까운 지 판별하여

가까운 방향으로 한 칸씩 이동시키고 cnt++ 을 수행한다.

이는 추출하고자 하는 원소의 인덱스가 0 일 때까지 반복된다.

 

이러한 과정을 거쳐 2, 3 연산이 수행된 횟수 cnt 를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    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());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Deque<Integer> dq = new LinkedList<>();

        for (int i = 1; i <= n; i++)
            dq.offer(i);

        st = new StringTokenizer(br.readLine());
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());

            while (true) {
                int idx = 0;
                for (int tmp : dq) {
                    if (tmp == num)
                        break;
                    idx++;
                }

                if (idx == 0) {
                    dq.pollFirst();
                    break;
                }

                if (idx > dq.size() / 2)
                    dq.addFirst(dq.removeLast());
                else
                    dq.addLast(dq.removeFirst());

                cnt++;
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
    }

}