[Kotlin] BOJ 28278. 스택2

출처

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

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

1. 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2. 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3. 3: 스택에 들어있는 정수의 개수를 출력한다.
4. 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5. 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

 

 

 

풀이

Stack 이란?

후입선출(Last-In First-Out, LIFO) 구조로, 끝에서만 데이터에 접근할 수 있는 자료구조

출처 : 위키피디아

 

마치 쌓아 올린 팬케이크처럼...위에서부터 팬케이크를 꺼내먹듯이 데이터를 사용할 수 있는 것이다.

Designed by Freepik

Stack 자료형의 사용은 다음과 같이 Stack 클래스를 사용하면 편하다. 그러나...

import java.util.Scanner
import java.util.Stack

private val stack = Stack<Int>()
fun main() = with(Scanner(System.`in`)) {
    val N = nextInt()
    repeat(N) {
        val m = nextInt()
        when {
            m == 1 -> {
                val x = nextInt()
                stack.push(x)
            }
            m == 2 -> {
                if (stack.empty()) println("-1")
                else println("${stack.pop()}")
            }
            m == 3 -> {
                println("${stack.size}")
            }
            m == 4 -> {
                if (stack.empty()) println("1")
                else println("0")
            }
            m == 5 -> {
                if (stack.empty()) println("-1")
                else println("${stack.peek()}")
            }
        }
    }
}

 

당연하게도 시간 초과가 발생한다! 이유는 여러가지...

 

1. Stack 라이브러리 성능 문제 : Stack은 Vector를 상속받는데, 이로 인해 불필요한 오버헤드가 발생하기 때문.

 

2. 입력 처리 속도 저하 : split() 메소드를 사용하는 것은 상당한 시간이 소요될 수 있고, 특히 많은 입력을 처리할 때 시간 초과가 발생했다. (100만개의 입력이 발생할 수 있음)

val m = br.readLine().split(" ").map { it.toInt() }

기존의 입력 처리 방식을

val br = BufferedReader(InputStreamReader(System.`in`))
val N = br.readLine().toInt()
...
val st = StringTokenizer(br.readLine())
val m = st.nextToken().toInt()
val x = st.nextToken().toInt()

와 같이 사용하자.

 

3. 출력 처리 속도 저하 : println을 반복적으로 호출하는 경우 출력 버퍼링이 일어날 수 있기 때문이다.

만약 String + String으로 이어붙이려고 해도 이와 같은 문제가 발생하기 때문에 StringBuilder를 사용하자.

 

 

답안

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()
    val N = br.readLine().toInt()
    val stack = Array(1000000) {0}
    var top = -1
    repeat(N) {
        val st = StringTokenizer(br.readLine())
        when (st.nextToken().toInt()){
            1 -> {
                stack[++top] = st.nextToken().toInt()
            }
            2 -> {
                if (top == -1) sb.append("-1\n")
                else {
                    sb.append("${stack[top--]}\n")
                }
            }
            3 -> {
                sb.append("${top+1}\n")
            }
            4 -> {
                if (top == -1) sb.append("1\n")
                else sb.append("0\n")
            }
            5 -> {
                if (top == -1) sb.append("-1\n")
                else sb.append("${stack[top]}\n")
            }
        }
    }
    println(sb.toString())
}