[1021] 회전하는 큐

[Silver III] 회전하는 큐 - 1021

문제 링크

성능 요약

메모리: 14504 KB, 시간: 136 ms

분류

자료 구조, 덱

문제 설명

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a₁, ..., a_k이었던 것이 a₂, ..., a_k와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a₁, ..., a_k가 a₂, ..., a_k, a₁이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a₁, ..., a_k가 a_k, a₁, ..., a_k-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

아이디어

처음엔 배열의 index를 이용해서 직접 구현해보려고 했는데, 생각보다 고려해야될 경우(index가 범위를 벗어나면 다시 처음 index로 가야하는 등)가 좀 있어서 다른 방법으로 접근했다. Queue를 이용하여 쉽게 풀 수 있었다.
다만 주의해야할 부분은 습관적으로 Queue 선언을 할 때 다음과 같이 했다는 것이다.

import java.util.*;

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

// deque.indexOf(target): 당연히 안 되는 부분..

구현체로 LinkedList를 썼다하더라도 변수의 Type을 Deque으로 선언해주었기 때문에 해당 참조변수로 indexOf를 호출할 수 있을리 없다. 기본적인 건데 실수해서 시간을 잡아먹었던 것 같다. 주의하도록 하자.

답안코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   // 큐의 크기
        int m = Integer.parseInt(st.nextToken());   // 뽑아내는 수의 크기

        // 뽑아내야하는 수를 담은 배열
        int[] targetArray = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        // 원형 큐 초기화
        LinkedList<Integer> circularQueue = new LinkedList<>();
        for (int i = 1; i < n + 1; i++) {
            circularQueue.add(i);
        }

        int leftCount = 0;
        int rightCount = 0;

        // 제거 대상을 하나씩 제거
        for (int target : targetArray) {
            int idx = circularQueue.indexOf(target);

            if (idx <= circularQueue.size() / 2) {   // 좌측 이동
                while (circularQueue.indexOf(target) != 0) {
                    int tmp = circularQueue.removeFirst();
                    circularQueue.addLast(tmp);
                    leftCount += 1;
                }
            } else {    // 우측 이동
                while (circularQueue.indexOf(target) != 0) {
                    int tmp = circularQueue.removeLast();
                    circularQueue.addFirst(tmp);
                    rightCount += 1;
                }
            }

            circularQueue.removeFirst();    // 큐 이동이 끝난 후 맨 앞에 온 target을 제거
        }

        System.out.println(leftCount + rightCount);
    }
}

BOJ 카테고리 내 다른 글 보러가기