[Kotlin] 백준 1021 : 회전하는 큐

문제 링크

1021번: 회전하는 큐

---

문제 해설

덱의 양방향 삽입, 삭제 연산을 통해 회전하는 큐를 구현할 수 있다. 

 

수를 뽑아내기 위한 인덱스는 항상 가장 앞으로 고정되어 있으므로 주어진 입력의 순서대로 수를 뽑으려면 원소들을 좌우로 이동시키면서 주어진 수가 가장 앞으로 오게 만들어야 한다. 예제 2의 경우는 아래 그림과 같은 과정을 거치게 된다.

이 때 뽑아낼 수가 큐의 가장 앞에 오려면 왼쪽 또는 오른쪽 중에 더 가까운 쪽으로 \(x\)번 수를 이동시켜야 한다. 이 방향은 큐에서 원소의 위치를 찾으면 쉽게 알 수 있다. indexOf()가 앞에서부터 원소의 위치를 찾아주므로 해당 값이 왼쪽으로 이동해야 하는 횟수가 되고, 큐의 크기에서 이 값을 빼면 오른쪽으로 이동해야 하는 횟수를 구할 수 있다.

 

각 경우에 대해 두 횟수를 구하여 더 적은 횟수인 방향으로 연산을 수행하고 수를 뽑아내면 된다.

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(' ').map(String::toInt)
    val deque = ArrayDeque<Int>().apply { for (i in 1..n) add(i) }
    val arr = StringTokenizer(readLine()).run { IntArray(m) { nextToken().toInt() } }
    var count = 0
    for (num in arr) {
        val left = deque.indexOf(num)
        val right = deque.size - left
        count += if (left < right) left else right
        if (left < right) repeat(left) { deque.addLast(deque.removeFirst()) }
        else repeat(right) { deque.addFirst(deque.removeLast()) }
        deque.removeFirst()
    }
    println(count)
}