꿈을 보는 개발자

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

입력받는 숫자를 HashMap<Long, Int> 형태로 key에 숫자 value에 나온 횟수를 각각 갱신해 주어서 HashMap의 최대값을 찾아서 출력하기만 하면 되는 간단한 문제였습니다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cards = HashMap<Long,Int>()

    repeat(readLine().toInt()){
        val key = readLine().toLong()
        if(cards[key] == null) cards[key] = 1
        else cards[key] = cards[key]!!+1
    }
    print(cards.filterValues { it == cards.maxOf { it.value }}.keys.minOrNull())
}

최초 답안은 다음과 같이 작성하였습니다. 각각 HashMap에 입력받은 값을 갱신하고 HashMap의 value의 최대값을 가지고 있는 key리스트를 분류하고 그중에서도 가장 작은 값의 key를 출력해주었습니다. 

하지만, 다음과 같이 시간초과가 나오게 되었습니다. 입력값의 범위가 -2^62 ~ 2^62 이므로 굉장히 크기때문에 발생하는 문제였습니다. 

다음과 같이 코드를 바꾸었습니다. 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cards = HashMap<Long,Int>()

    repeat(readLine().toInt()){
        val key = readLine().toLong()
        if(cards[key] == null) cards[key] = 1
        else cards[key] = cards[key]!!+1
    }
    val max = cards.maxOf { it.value }
    val keys = cards.filterValues { it == max }.keys
    print(keys.minOrNull())
}

filterValues 내부에서 계속해서 maxOf()함수를 불러서 O(n)만큼의 동작을 계속 해주었기때문에 그만큼 계속해서 탐색 시간이 길어졌고 이로 인해서 같은 동작이지만, 동작 시간이 굉장히 늘어났던 것입니다. 

간단한 코드 수정이지만, 평소에도 쓸데없는 동작을 피하는 코드작성을 하도록 유의해야겠습니다!

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

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

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

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

가장 처음 문제인 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들에 대한 시간복잡도도 다시 한번 상기 할 수 있었습니다.