baekjoon: 10989. 수 정렬하기 3

문제링크

• 제한 시간 : 1초
• n : 1 ~ 10,000,000
• O(N * logN) -> 약 2억 연산 -> x
• O(N) 해결 방법 필요
• 숫자 범위 : 1 ~ 10,000

Counting Sort

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

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    // n : 1 ~ 10,000,000
    val n = br.readLine().toInt()
    val counts = Array(10001) { 0 }
    for (i in 0 until n) {
        val num = br.readLine().toInt()
        counts[num]++
    }
    counts.forEachIndexed { index, count ->
        for (i in 0 until count) {
            bw.write("$index\n")
        }
    }
    br.close()
    bw.close()
}