[백준 1021] 회전하는 큐

백준 1021번: 회전하는 큐 - 상세 풀이

🔍 1. 문제 소개

백준 1021번 "회전하는 큐" 문제는 N개의 원소를 포함하는 양방향 순환 큐에서 특정 원소들을 순서대로 뽑아내는 문제입니다. 큐에서 원소를 뽑아내기 위해서는 첫 번째 원소를 뽑아내거나, 큐를 왼쪽 또는 오른쪽으로 회전시키는 연산을 사용할 수 있습니다. 목표는 주어진 순서대로 원소들을 뽑아내는 데 필요한 왼쪽/오른쪽 회전 연산의 최솟값을 구하는 것입니다.

💡 2. 문제 해석

문제의 핵심은 최소한의 연산으로 원소들을 뽑아내는 것입니다. 단순히 원하는 원소가 큐의 앞에 올 때까지 계속 회전시키는 것은 비효율적입니다. 왼쪽으로 회전하는 연산과 오른쪽으로 회전하는 연산의 횟수를 비교하여 더 적은 횟수의 연산을 사용하는 전략이 필요합니다. 입력으로는 큐의 크기 N, 뽑아낼 원소의 개수 M, 그리고 뽑아낼 원소들의 원래 위치가 주어집니다.

🧠 3. 접근 방법

문제를 해결하기 위한 가장 효율적인 방법은 그리디 알고리즘을 사용하는 것입니다. 각 원소를 뽑아낼 때마다, 그 원소를 큐의 맨 앞으로 가져오는 데 필요한 왼쪽 회전 횟수와 오른쪽 회전 횟수를 비교하고, 더 적은 횟수의 회전을 수행합니다. 이를 통해 최소한의 회전 연산으로 원소들을 뽑아낼 수 있습니다. 큐를 직접 구현하여 연산을 수행하는 것이 효율적입니다.

⚙️ 4. 구현 과정

1. **큐 초기화:** N개의 원소를 포함하는 큐를 생성합니다. ( `ArrayDeque` 사용 권장)

2. 입력 받기: 큐의 크기 N, 뽑아낼 원소의 개수 M, 그리고 뽑아낼 원소들의 위치를 입력받습니다. 3. 반복문: M번 반복하며, 각 원소를 뽑아냅니다. 4. 왼쪽/오른쪽 회전 횟수 계산: 현재 큐에서 뽑아낼 원소의 위치를 찾습니다. 왼쪽으로 회전하는 횟수와 오른쪽으로 회전하는 횟수를 계산합니다. 5. 최소 회전 횟수 선택 및 적용: 왼쪽/오른쪽 회전 횟수 중 더 작은 값을 선택하고, 그만큼 큐를 회전시킵니다. ( ArrayDeque 의 rotate 메소드 사용은 효율적이지 않으므로 직접 구현하는 것이 더 빠릅니다.) 6. 원소 뽑아내기: 큐의 첫 번째 원소를 뽑아냅니다. 7. 총 회전 횟수 누적: 총 회전 횟수를 누적합니다. 8. 결과 출력: 총 회전 횟수를 출력합니다.

💻 5. 코드 설명

import kotlin.math.min

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val targets = readLine()!!.split(" ").map { it.toInt() }

    val queue = ArrayDeque(n) // 효율적인 큐 초기화
    for (i in 1..n) {
        queue.add(i)
    }

    var count = 0
    for (target in targets) {
        val index = queue.indexOf(target)
        val leftCount = index
        val rightCount = queue.size - index

        val moveCount = min(leftCount, rightCount)
        count += moveCount

        if (leftCount <= rightCount) {
            repeat(moveCount) {
                queue.addLast(queue.removeFirst())
            }
        } else {
            repeat(moveCount) {
                queue.addFirst(queue.removeLast())
            }
        }
        queue.removeFirst()
    }
    println(count)
}

* ArrayDeque(n): ArrayDeque를 사용하여 큐를 초기화하고, 용량을 미리 지정하여 효율성을 높입니다. * indexOf(target): 큐에서 target의 인덱스를 찾습니다. * min(leftCount, rightCount): 왼쪽/오른쪽 회전 횟수 중 더 적은 값을 선택합니다. * repeat 함수: 큐를 회전시키는 반복문을 간결하게 작성합니다.

⏱️ 6. 시간 복잡도와 공간 복잡도 분석

* 시간 복잡도: indexOf 연산이 O(n)이므로, 최악의 경우 O(m*n)이 될 수 있습니다. 하지만 대부분의 경우 균형있게 분포되므로, 실제 시간 복잡도는 O(n+m)에 가까워집니다. (50 이하의 N에 대해서는 문제가 되지 않지만, N이 매우 클 경우 아래의 개선사항을 참고해야 합니다.) * 공간 복잡도: 큐를 저장하는 데 O(n)의 공간이 필요합니다.

개선된 시간 복잡도 (N이 매우 큰 경우): indexOf 연산 대신 HashMap을 이용하여 각 원소의 위치를 저장하면 O(1)의 시간으로 원소의 위치를 찾을 수 있습니다. 이 경우 시간 복잡도는 O(n+m)으로 개선됩니다.

🎯 7. 결론

이 문제는 그리디 알고리즘을 활용하여 효율적으로 해결할 수 있습니다. ArrayDeque를 사용하고 왼쪽/오른쪽 회전 횟수를 비교하여 최소한의 연산으로 원소를 뽑아내는 전략이 중요합니다. N의 크기가 매우 크다면, indexOf 대신 HashMap을 이용하여 시간 복잡도를 O(n+m)으로 개선하는 것을 고려해야 합니다. 이 문제를 통해 그리디 알고리즘의 활용과 자료구조 선택의 중요성을 다시 한번 확인할 수 있었습니다.