[백준/BOJ] 1021번: 회전하는 큐

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

1021번: 회전하는 큐

문제

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

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

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

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

해설

덱(deque)을 사용하면 어렵지 않게 풀 수 있는 문제이다.

뽑아내려고 하는 수의 위치가 덱의 첫번째라면 1번 연산을 하면 된다.

덱의 크기 / 2를 한 값보다 작거나 같다면 2번 연산을 통해 맨 앞의 원소를 덱의 나중 위치로 옮기고

그게 아니라면 맨 뒤의 원소를 맨 앞으로 옮기면 된다.

1번 연산이 아닐 시 count++를 해줌으로써 2, 3번 연산이 몇번 실행되는지 알아내면 된다.

소스 코드

import java.util.*

fun main() {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val deq:Deque<Int> = LinkedList()
    for(i in 1..n) deq.offer(i)
    st = StringTokenizer(readLine())
    var count = 0
    for(i in 0 until m) {
        var check = false
        val element = st.nextToken().toInt()
        while(!check) {
            if(element == deq.first) {
                deq.pollFirst()
                check = true
            }
            else {
                if(deq.indexOf(element) <= deq.size / 2) deq.offerLast(deq.pollFirst())
                else deq.offerFirst(deq.pollLast())
                count++
            }
        }
    }
    println(count)
}