[백준] 1966 (프린터 큐)

#1 알고리즘

#1-1 큐

[백준] 10845 - 큐

큐(Queue)가 사용되었다는 점에서 비슷한 문제다.

 

#1-2 목표 문서의 인덱스

프린트할 목표 문서의 인덱스를 어떤 변수 A로 두고 추적할 수도 있다. 하지만 이러면 Queue가 offer되거나 poll될 때에 바뀌는 목표 문서의 위치에 맞게 A의 값을 계속 조정해주어야 한다. 이는 가독성에 나쁜 영향을 미치고, 그래서 에러의 여지를 키운다. 나는 코틀린의 Pair 객체를 이용해서, 목표 문서가 목표 문서임을 알 수 있게 표시하여 Queue에 넣었다.

 

#2 코드 - 코틀린

import java.util.LinkedList
import java.util.Queue

fun main() {
    val testCaseCount = readln().toInt()
    for(i: Int in 0..<testCaseCount) {
        // 첫째 줄 읽어들이기
        val printerInformation = readln().split(" ")
        val fileCount = printerInformation[0].toInt()
        val targetFileIndex = printerInformation[1].toInt()

        // 둘째 줄 읽어들이기
        val fileStrings = readln().split(" ")
        val fileQueue: Queue<Pair<Int, String>> = LinkedList()
        for(j: Int in 0..<fileCount) {
            if(j == targetFileIndex) {
                fileQueue.offer(Pair(fileStrings[j].toInt(),"target"))
            } else {
                fileQueue.offer(Pair(fileStrings[j].toInt(),""))
            }
        }

        // 출력
        println(getTargetOrder(fileQueue))
    }
}

fun getTargetOrder(queue: Queue<Pair<Int, String>>): Int {
    var order = 1

    while(true) {
        if(isHighestPriorityOfPeek(queue)) { // peek한 원소가 최고 우선순위면
            if(queue.poll().second == "target") {
                return order
            }
            order++
        } else { // peek한 원소가 최고 우선순위가 아니면
            queue.offer(queue.poll())
        }
    }
}

fun isHighestPriorityOfPeek(queue: Queue<Pair<Int, String>>): Boolean {
    val peekedElement = queue.peek().first

    for(i: Int in 1..<queue.size) {
        if(peekedElement < queue.elementAt(i).first) {
            return false
        }
    }

    return true
}