Kotlin] 백준 10989번 문제풀이

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

10989번: 수 정렬하기 3

 

 

이 문제는.. 최대 천만개의 숫자를 정렬해야한다. 따라서 평범한 sorting방식을 사용할 수 없다. 왜냐면 sorting은 k개의 요소를 가진 배열의 n번째의 숫자를 1~k까지 훑어서 위치를 정하는 방식이기 때문에 결국 O^2 방식의 시간복잡도를 가진다. 따라서 배열의 갯수가 커질수록 기하급수적으로 커지고, 10^7개의 배열은 결국 10^14번 도는 것이기 때문에, 그리고 이것을 프린팅까지 해야하므로 조건으로 제시한 3초 내에 통과하기란 절대 불가능하다.

 

간단하게 예시로 살펴보자.

import kotlin.system.measureTimeMillis

fun main(args: Array<String>) {
    val elapsed : Long = measureTimeMillis {
        question10989()
    }

    println(elapsed)
}

fun question10989() {
    val count = readln().toInt()
    val list = mutableListOf<Int>()

    for(i in 0 ..< count) {
        val number = readln().toInt()
        list.add(number)
    }

    println(list.joinToString("\n"))
    println("----")
}

 

이게 간단하게 배열에 넣어서 값을 sorting하는 방식이다.

테스트를 위해 가볍게 랜덤한 숫자 10만개만 넣어 테스트 해보았다.

 

10만개만 되도 벌써 4초가 걸린다. println의 방식을 이용했다 하더라도, 아마 천만개 풀로 들어온다면 버퍼를 이용해도 백퍼 시간 턱에 걸릴 건 당연하다. 그럼 이걸 어떻게 푸는데;

 

이 문제의 해답은 들어오는 숫자의 범위가 1~10000까지라는 점이다.

따라서 이 문제는 이 문제를 들어올때 백준이 적어둔 힌트인

수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

 

를 이용해야한다.

카운팅 정렬이란 키 값을 이용해서 정렬하는 방식으로, 이 문제의 경우 숫자 자체가 곧 키가 된다.

이게 뭔소린고,, 싶을텐데.

 

뭐.. 맵에 key:value를 넣거나 하는 방식이 있을수도 있겠으나.. 나같은 경우는 배열을 숫자배열만큼 만들어놓고, 숫자가 들어올때마다 해당 위치의 배열 숫자를 +1 하는 방식을 채택했다.

예를 들어 5라는 숫자가 들어오면

arr[5] += 1

 

을 해주는거다. 그러면 콘솔로 들어오는 횟수 O(n), 그리고 1만개의 배열을 도는 시간 + 10000을 하면 값을 정렬할 수 있다.

 

그리고 여기서 두번째, println으로 일일히 풀면 줄마다 print -> write -> newLine()의 공정을 또 배열의 시간만큼 추가하게 된다.

따라서, 버퍼에 값을 한번에 담아 flush 하면 배열만큼 드는 시간은 string을 추가하는 시간 뿐이고, print -> write를 한번에 진행하므로 println보다는 buffer flush를 하는게 시간 절약에 도움이 된다. 

 

이를 코드로 옮기면

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main(args: Array<String>) {
    question10989()
}

fun question10989() {

    var reader = BufferedReader(InputStreamReader(System.`in`))
    var writer = BufferedWriter(OutputStreamWriter(System.out))

    val count = reader.readLine().toInt()
    val list = Array<Int>(10001) {0}

    for(i in 0 ..< count) {
        val number = reader.readLine().toInt()
        list[number] += 1
    }


    for(i in 0 ..< list.count()) {
        if(list[i] > 0) {
            repeat(list[i]) {
                writer.write("$i")
                writer.newLine()
            }
        }
    }

    writer.flush()
    println("---")


}

 

이 코드에 걸리는 시간을 보자.

 

앞서 코드보다 시간이 획기적으로 줄어드는 것을 확인할 수 있다.

 

 

 ps. 장렬한 고민의 흔적들..