https://www.acmicpc.net/problem/10828
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
https://www.acmicpc.net/problem/10845
10845번: 큐
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
https://www.acmicpc.net/problem/10866
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
기본 자료구조 복습을 위해 연계되어있는 상단의 세문제들을 풀어보았습니다. 이 과정에서 시간초과의 중요성을 알게 되었습니다.
가장 처음 문제인 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를 사용하였습니다. 그제서야 문제해결을 할 수 있었습니다.
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를 사용한 입출력을 통해서 성공 할 수 있었습니다.
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들에 대한 시간복잡도도 다시 한번 상기 할 수 있었습니다.
'Kotlin(PS) > 기타' 카테고리의 다른 글
11652 카드(Kotlin) (1) | 2022.09.23 |
---|