Queue(큐) feat.kotlin

정의

 

기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다.

queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

 

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

1158번: 요세푸스 문제

Queue를 이용하여,  쉽게 무언가 지금 규칙에 맞지 않지만, 추후에 반드시 작업을 해주어야 한다면... 재삽입을 통해 1열로 대기시킨다. 

 

예시)

제거 되지 않은 숫자를 다시 뒤에 삽입한다.

k에 맞춰 제거될 수를 따로 보관한다.

위 행동을 큐가 모두 비워질 때까지 반복한다.

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

var n = 0
var k = 0

val q: Queue<Int> = LinkedList()
val result = mutableListOf<Int>()
fun main() = with(System.`in`.bufferedReader()) {

    val info = readLine().split(" ").map { it.toInt() }
    n = info[0]
    k = info[1]

    for (i in 1..n) {
        q.add(i)
    }

    while (q.isNotEmpty()) {
        for (i in 1 .. k) {
            val num = q.poll()
            if (i == k)
                result.add(num)
            else
                q.add(num)
        }
    }

    println("<${result.joinToString(", ")}>")
}

 

 

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

13335번: 트럭

 

2개의 Queue를 이용하여,

다리와 대기하는 트럭의 상태를 구현하면 쉽게 해결할 수 있는 문제이다.

import java.util.*

var n = 0
var w = 0
var l = 0

lateinit var truckArr: IntArray

val waitingQueue: Queue<Int> = LinkedList()
val bridge: Queue<Truck> = LinkedList()

data class Truck(var weight: Int, var position: Int)

fun main() = with(System.`in`.bufferedReader()){

    val info = readLine().split(" ").map { it.toInt() }
    n = info[0]
    w = info[1]
    l = info[2]

    // 모든 트럭을 대기 큐에 넣는다.
    truckArr = readLine().split(" ").map { it.toInt() }.toIntArray()
    for (i in 0 until truckArr.size) {
        waitingQueue.add(truckArr[i])
    }

    val completeList = mutableListOf<Truck>()

    var time = 0
    while (truckArr.size > completeList.size) {
        time += 1

        // 다리 위의 트럭을 이동시킨다.
        if (bridge.isNotEmpty()) {
            // 다리위 트럭 1칸씩 이동.
            bridge.map { it.position += 1 }
            if (bridge.peek().position > w) {
                completeList.add(bridge.poll())
            }
        }

        // 대기 하는 트럭을 다리 위로 올려보낸다.
        if (waitingQueue.isNotEmpty()) {
            val bridgeWeight = bridge.sumOf { it.weight }
            val restWeight = l - bridgeWeight
            // 다리의 하중에 더 올라갈 여유가 있고, 다리위에 트럭이 올라갈 공간이 있다면
            if (restWeight >= waitingQueue.peek() && w > bridge.size)
                bridge.add(Truck(waitingQueue.poll(), 1))
        }
    }

    println(time)
}