꿈을 보는 개발자

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

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

처음 시도에서는 가장 보편적인 방법인 재귀를 통해서 문제풀이를 시도하였습니다. 하지만 시간초과의 결과가 나오게 되었습니다.

fun main() {
    val n = readLine()!!.toInt()
    fun fibo(n: Int): Int {
        if (n == 0) return 0
        if (n == 1) return 1
        return fibo(n - 1) + fibo(n - 2)
    }
    print(fibo(n))
}

따라서 재귀호출이 끝나고 현재 함수에서는 추가적인 연산을 하지 않게끔 해주어 마치 for loop와 동일한 효과를 발생하는 tailrec 키워드의 꼬리재귀를 사용하였습니다. 

fun main() {
    val n = readLine()!!.toInt()

    tailrec fun fibo(n: Int , pre:Int, next:Int): Int {
        if (n <= 0) return pre
        return fibo(n - 1, next, pre +next)
    }
    print(fibo(n,0,1))
}

매개변수로는 n-1 n-2 변수 대용으로 n-1 next와 이전에 계산한 합을 넘겨줍니다.

Koltlin을 통해서 백준을 준비하던중 하나 궁금한 점이 생겼습니다. 

기본적으로 Kotlin을 통해서 사용할 수 있는 입출력 함수는 다음 세가지 입니다. 

1. Scanner

2. BufferedReader

3. Java라이브러리를 확장한 Kotlin 자체 Console I/O

총 세가지 입니다. 자체적으로 입력을 받는다면 속도측정에 편차가 발생하는 것이 우려되어서 백준의 간단한 입출력 문제를 기준으로 속도측정 해봤습니다. 

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

다음 문제를 풀기 위해서 총 세가지 형태로 입출력을 받는 코드를 작성해봤습니다. 

1. Scanner

import java.util.*

fun main()  = with(Scanner(System.`in`)){
    val (n,m)= readLine()!!.split(" ").map { it.toInt() }
    if(n>m) println(">")
    else if(n<m) println("<")
    else println("==")
}

2.BufferedReader

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val (n,m)= readLine()!!.split(" ").map { it.toInt() }
    if(n>m) println(">")
    else if(n<m) println("<")
    else println("==")
}

3. Kotlin Console I/O

fun main(){
    val (n,m)= readLine()!!.split(" ").map { it.toInt() }
    if(n>m) println(">")
    else if(n<m) println("<")
    else println("==")
}

해당 코드들을 각각 실행시켜봤습니다. 플랫폼 특성항 4~5ms의 편차는 발생할 수 있지만, 평균적인 속도는 다음과 같았습니다.

BufferdReader가 메모리와 시간순으로는 가장 효율적이었으며,

Kotlin Console은 시간면에서는 근소하게 느렸으며 메모리측면으로는 BufferdReader보다 효율적이지 못했습니다.  

Scanner는 시간, 메모리 측면에서 모두 좋지 않은 성능을 보여주었습니다. 

하지만, 개인적으로는 BufferedReader를 with 함수로 main함수 전체에서 쓸 수 있도록 해주었지만 다른 경우에는 객체를 선언하고 메모리 누수방지를 위해 객체 반환을 해주어야하므로 코드의 가독성 측면에서는 Kotlin Console I/O가 우수한 상황이 나올수도 있기 때문에 각자의 상황에 따라 적절하게 사용하는 것이 중요할 것입니다.

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

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

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

백트래킹의 연습을 위해서 문제를 풀었습니다. 가장 중요한 구조는 N과 M(1) 의 문제를 기초로 문제에서 원하는 조건 과 분기를 설정하여 백트래킹을 하는 것입니다.

fun main(){
    val (n,m) = readLine()!!.split(" ").map{it.toInt()}
    val num = IntArray(m) {0}
    val used = BooleanArray(n+1) {false}


    fun bt(par : Int){
        if(m==par) {
            println(num.joinToString(" "))
            return
        }
        
        for(i in 1..n){
            if(!used[i]){
                num[par] =  i
                used[i]= true
                bt(par+1)
                used[i]=false
            }
        }
    }
    bt(0)
}

n을 사용되는 숫자의 범위 m을 출력될 자리수로 생각하면 bt함수의 첫번째에서는 우선 자리수(m)만큼 bt함수가 재귀 되었는가를 판단하고 만약 그만큼 재귀되었다면 채워진 num IntArray를 출력하는 것입니다. 

이후 for문에서는 used라는 BoolenArray를 통해서 해당 숫자가 사용되었는가 아닌가를 판단하면서 사용되지 않았다면 해당 숫자를 num에 채우고 다음 숫자를 매개변수로 재귀 호출 합니다. 

이와 같은 구조를 기초로 N-Queen, 부분수열의 합등의 문제를 풀었습니다.

이외 풀이 코드는 https://github.com/IslandofDream/Baekjoon_Practice/tree/main/%EB%B0%B1%EC%A4%80 를 참고해주시면 감사하겠습니다.

참고링크

https://blog.encrypted.gg/945

https://youngest-programming.tistory.com/221