[백준 10845번] [Kotlin] 큐

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

10845번: 큐

 

난이도 : 실버 4
태그 : 큐, 자료구조

 

---

설명

 

이전에 포스팅했던 스택(https://uknowblog.tistory.com/11?category=989901)과 같이,

 

자료구조 큐를 사용하는 문제입니다.

 

---

소스코드

fun main() {
    var right = -1
    var left = 0
    val queue: Array<Int>

    val n = readLine()!!.toInt()
    queue = Array(n) { 0 }

    repeat(n) {
        when (val input = readLine()!!) {
            "pop" -> {
                if (left > right) {
                    println(-1)
                } else {
                    println(queue[left++])
                }
            }

            "size" -> {
                if (left > right) {
                    println(0)
                } else {
                    println(right - left + 1)
                }
            }

            "empty" -> {
                println(if (left > right) 1 else 0)
            }

            "front" -> {
                if (left > right) {
                    println(-1)
                } else {
                    println(queue[left])
                }
            }

            "back" -> {
                if (left > right) {
                    println(-1)
                } else {
                    println(queue[right])
                }
            }

            // Push X
            else -> {
                val number = input.split(" ")[1].toInt()
                queue[++right] = number
            }
        }
    }
}

 

끝부분만 알면 되기에, 포인터 하나가 필요했던 스택과 달리

끝과 시작을 가르킬 포인터 두개가 필요합니다.

본 포스팅에서는 left, right 라는 이름으로 변수명을 지었습니다.

 

배열의 크기는 무조건 인풋값으로 주어지는 n 이하이므로, 배열 queue의 크기는 n으로 잡았습니다.

 

"pop" -> {
    if (left > right) {
        println(-1)
    } else {
        println(queue[left++])
    }
}

pop 연산의 경우, left가 right보다 크다면 (값이 하나도 없다면) -1을 반환하며,

값이 있을 경우 queue의 시작부분 원소를 꺼내고, 시작부분 포인터(left)를 1만큼 늘립니다.

 

 

"size" -> {
    if (left > right) {
        println(0)
    } else {
        println(right - left + 1)
    }
}

사이즈의 경우 끝 포인터에서 시작 포인터를 뺀 후, 1만큼 늘려주어야 합니다.

 

 

"front" -> {
    if (left > right) {
        println(-1)
    } else {
        println(queue[left])
    }
}

"back" -> {
    if (left > right) {
        println(-1)
    } else {
        println(queue[right])
    }
}

큐의 맨 끝, 맨 처음 원소를 보는 front와 back은 각각의 포인터가 가리키는 원소를 출력합니다.

 

 

// Push X
else -> {
    val number = input.split(" ")[1].toInt()
    queue[++right] = number
}

push 연산의 경우, 끝 포인터를 1만큼 증가하고, 그 자리에 새 원소를 넣습니다.

 

 

---

후기

 

스택에 이어 큐 역시 직접 구현해보았습니다.

 

사실 스택이나 큐 같은 자료구조는 많은 언어들이 자체적으로 지원하기에,

 

코딩테스트나 현업에서는 직접 구현하기 보단 자체적으로 지원하는 자료구조를 많이 씁니다만,

 

모처럼 백준 문제로 만나봤기도 하니, 한번쯤 직접 구현해보는 것도 나쁘진 않은 것 같습니다