[백준/10845] 큐 (Kotlin)

문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 여섯 가지이다.push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력과 출력

 

답안

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val bufferedWriter = BufferedWriter(OutputStreamWriter(System.out))

    val queue: Queue<Int> = LinkedList()

    repeat(bufferedReader.readLine().toInt()){
        val str = StringTokenizer(bufferedReader.readLine())
        when(str.nextToken()){
            "push" -> queue.add(str.nextToken().toInt())
            "pop" -> bufferedWriter.write(
                (if (queue.isEmpty()) -1 else queue.poll()).toString() + "\n"
            )
            "size" -> bufferedWriter.write(
                queue.size.toString() + "\n"
            )
            "empty" -> bufferedWriter.write(
                (if (queue.isEmpty()) 1 else 0).toString() + "\n"
            )
            "front" -> bufferedWriter.write(
                (if (queue.isEmpty()) -1 else queue.peek()).toString() + "\n"
            )
            "back" -> bufferedWriter.write(
                (if (queue.isEmpty()) -1 else queue.last()).toString() + "\n"
            )
        }
    }

    bufferedReader.close()
    bufferedWriter.flush()
}

 

풀이

 

세부 구현 방법

• BufferedReader로 첫 줄을 읽고 명령어 개수(N)를 저장한다.
• repeat(N)으로 반복문을 돌면서 매 줄마다 명령어를 입력받고, StringTokenizer로 명령어를 분리한다.
• push는 큐에 add하고, pop, front, back은 비어있을 경우 -1, 아니면 해당 값을 출력한다.
• size는 큐 크기 출력, empty는 비었으면 1, 아니면 0을 출력한다.
• 모든 명령 처리가 끝난 후 bufferedReader.close(), bufferedWriter.flush()로 입출력을 마무리한다.

 

주의사항 및 성능 포인트

• BufferedReader, BufferedWriter를 사용해 대량 입출력에서도 시간 초과를 방지했다.
• Queue 자료구조는 LinkedList를 이용해 구현했다. (Kotlin 기본 Queue는 인터페이스고, 실제 구현체가 필요해서 LinkedList 사용)
• poll(), peek()은 큐가 비어있으면 null을 반환할 수 있으므로, 반드시 isEmpty()로 먼저 확인했다.
• flush()는 매 명령어마다 하지 않고, 마지막에 한 번만 호출하여 출력 성능을 최적화했다.

 

기본 개념 정리

 

Queue

• FIFO(First In, First Out) 구조를 가진 자료구조이다.
• 즉, 먼저 들어온 데이터가 먼저 나간다.
• Kotlin에서는 Queue 인터페이스를 사용하고, 주로 LinkedList로 구현한다.

 

add(x: Int)

• 큐의 뒤쪽에 정수 x를 추가한다.
• 공간이 부족하면 예외가 발생할 수 있지만, LinkedList 기반이므로 거의 발생하지 않는다.

 

poll()

• 큐의 맨 앞(front) 에 있는 요소를 제거하고 반환한다.
• 큐가 비어있으면 null을 반환한다.

 

peek()

• 큐의 맨 앞(front) 에 있는 요소를 반환하지만, 제거하지 않는다.
• 큐가 비어있으면 null을 반환한다.

 

isEmpty()

• 큐가 비어있으면 true, 하나라도 요소가 있으면 false를 반환한다.

 

size

• 큐에 들어있는 요소의 개수를 반환한다.
• 프로퍼티처럼 바로 접근 가능하다.

 

last()

• Kotlin의 Queue에는 기본적으로 back 메서드가 없기 때문에,
  LinkedList를 이용할 경우 확장함수 last()를 사용해서 맨 뒤(back) 요소를 가져올 수 있다.