[백준] 1021. 회전하는 큐

문제 링크

[백준] 1021. 회전하는 큐

풀이 과정

덱 자료구조를 사용하는 문제입니다. 이동시키는 연산에서 뽑을 요소의 위치를 알아야 어느 방향으로 이동시키는 것이 최적인지 알 수 있습니다.

LinkedList<Integer> deque = new LinkedList<>();
for (int i = 1; i <= N; i++) deque.add(i);

Linked 구조는 indexOf 메서드를 사용할 수 있으므로 덱을 LinkedList로 구현합니다. 이후, 1부터 N까지의 수들을 덱에 넣어줍니다.

for (int i = 0; i < M; i++) {
    int target = sc.nextInt();
    int targetIdx = deque.indexOf(target);
    int size = deque.size();

    if (targetIdx == -1) continue;

    if (targetIdx <= size / 2) {
        while (deque.peekFirst() != target) {
            deque.addLast(deque.pollFirst());
            answer++;
        }
        deque.pollFirst();
    } else {
        while (deque.peekFirst() != target) {
            deque.addFirst(deque.pollLast());
            answer++;
        }
        deque.pollFirst();
    }
}

뽑아내려는 수 target을 입력받아, 해당 요소가 위치하는 인덱스 targetIdx를 구합니다. targetIdx가 덱의 중앙보다 좌측에 위치하면 왼쪽으로 이동시키는 연산을, 중앙보다 우측에 위치하면 오른쪽으로 이동시키는 연산을 적용합니다.

코드

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int answer = 0;

        LinkedList<Integer> deque = new LinkedList<>();
        for (int i = 1; i <= N; i++) deque.add(i);

        for (int i = 0; i < M; i++) {
            int target = sc.nextInt();
            int targetIdx = deque.indexOf(target);
            int size = deque.size();

            if (targetIdx == -1) continue;

            if (targetIdx <= size / 2) {
                while (deque.peekFirst() != target) {
                    deque.addLast(deque.pollFirst());
                    answer++;
                }
                deque.pollFirst();
            } else {
                while (deque.peekFirst() != target) {
                    deque.addFirst(deque.pollLast());
                    answer++;
                }
                deque.pollFirst();
            }
        }

        System.out.println(answer);
    }
}