Kotlin 자료구조 및 입출력 변화를 통한 시간 초과 해결

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

10828번: 스택

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

10845번: 큐

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

10866번: 덱

기본 자료구조 복습을 위해 연계되어있는 상단의 세문제들을 풀어보았습니다. 이 과정에서 시간초과의 중요성을 알게 되었습니다. 

 

 

10828 스택 제출 결과

가장 처음 문제인 stack문제의 경우 시간을 크게 생각하지 않고 kotlin의 대표적은 collection중 비교적 느린 MutableList를 통해 구현하고 입출력도 kotlin Console I/O와 print 함수를 사용하였습니다. 아슬아슬하게 시간이 초과되지는 않았습니다. 

fun main() {
    val n = readLine()!!.toInt()
    val stack = mutableListOf<Int>()
    for (i in 1..n) {
        val command = readLine()!!.split(" ")
        when (command[0]) {
            "push" -> stack.add(command[1].toInt())
            "pop" -> if (stack.isEmpty()) println("-1") else {
                println(stack.last())
                stack.removeLast()
            }
            "size" -> println(stack.size)
            "empty" -> if (stack.isEmpty()) println("1") else println("0")
            "top" -> if (stack.isEmpty()) println("-1") else println(stack.last())
        }
    }
}

 

스택 문제를 풀때 처럼 시간을 고려하지 않았더니 시간초과가 나오게 되었습니다. 따라서 이번에는 O(n)의 시간복잡도를 가진 MutableList보다는 메모리 효율은 떨어지지만 시간복잡도는 O(1)인 LinkedList를 사용하였습니다. 그제서야 문제해결을 할 수 있었습니다.

10845 큐 제출결과

 

import java.util.*

fun main() { 10845
    val n = readLine()!!.toInt()
    val queue = LinkedList<Int>()
    for (i in 1..n) {
        val command = readLine()!!.split(" ")
        when (command[0]) {
            "push" -> queue.add(command[1].toInt())
            "pop" -> if (queue.isEmpty()) println("-1") else {
                println(queue.first())
                queue.removeFirst()
            }
            "size" -> println(queue.size)
            "empty" -> if (queue.isEmpty()) println("1") else println("0")
            "front" -> if (queue.isEmpty()) println("-1") else println(queue.first())
            "back" -> if (queue.isEmpty()) println("-1") else println(queue.last())
        }
    }
}

 

마지막으로 덱 문제를 풀때도 역시 시간초과가 발생하였습니다. LinkedList를 통해서 시간초과를 해결하였으니 마지막으로는 입출력 부분에서의 시간낭비를 줄여야 했습니다. Kotlin Console I/O가 아닌 BufferedReader와 StringBuilder를 사용한 입출력을 통해서 성공 할 수 있었습니다.

10866 덱 문제 제출결과

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine()!!.toInt()
    val deque = LinkedList<Int>()
    val sb = StringBuilder()
    for (i in 1..n) {
        val command = readLine()!!.split(" ")
        when (command[0]) {
            "push_front" -> deque.add(0, command[1].toInt())
            "push_back" -> deque.add(deque.lastIndex+1, command[1].toInt())
            "pop_front" -> if (deque.isEmpty()) sb.append("-1\n") else {
                sb.append("${deque.first()}\n")
                deque.removeFirst()
            }
            "pop_back" -> if (deque.isEmpty()) sb.append("-1\n") else {
                sb.append("${deque.last()}\n")
                deque.removeLast()
            }
            "size" -> sb.append("${deque.size}\n")
            "empty" -> if (deque.isEmpty()) sb.append("1\n") else sb.append("0\n")
            "front" -> if (deque.isEmpty()) sb.append("-1\n") else sb.append("${deque.first()}\n")
            "back" -> if (deque.isEmpty()) sb.append("-1\n") else sb.append("${deque.last()}\n")
        }
    }
    print(sb)
}

결론적으로는 StringBuilder부분에서의 시간효율이 많이 개선되었던 것 같지만 Kotlin 기본 Collection들에 대한 시간복잡도도 다시 한번 상기 할 수 있었습니다.