[백준 10989] 수 정렬하기 3 | KOTLIN

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

문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

분류

• 정렬

시간제한

• Java 8: 3 초
• Java 8 (OpenJDK): 3 초
• Java 11: 3 초
• Kotlin (JVM): 3 초
• Java 15: 3 초

메모리 제한

• Java 8: 512 MB
• Java 8 (OpenJDK): 512 MB
• Java 11: 512 MB
• Kotlin (JVM): 512 MB
• Java 15: 512 MB

---

풀이

arrayList로 N 만큼 add 후 sort 로 해서 편리하다고 생각했으나 메모리 초과 떠서 구글링했다. (참고블로그 https://somjang.tistory.com/entry/Mxmxmxm )

10,000 칸 짜리 배열을 만들어서 N 만큼 입력받을 때 해당 숫자의 인덱스 요소를 1씩 증가한다.

10,000 칸 배열 순회하면서 0인 경우 출력안하고 1 이상일 경우 해당 카운트만큼 인덱스를 출력한다.

그래도 시간 초과 떠서 println, readLine() 보다 더 빠른 방법 있는지 검색했다.

BufferedReader 가 더 빠른건가보다,, 결국 다른 블로그 보고 정답만듦,,

코드

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

fun main() {
    val maxSize: Int = 10001
    // create a List of fixed-size
    val cntList: List<Int> = List(maxSize) { 0 } // listOf(10000) {0} // arrayListOf<Int>(0)
    val cntArr = cntList.toIntArray()
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()

    var numIndex: Int = 0

    for (i in 1..n) {
        numIndex = br.readLine()!!.toInt()
        //numIndex = BufferedReader(InputStreamReader(System.`in`)).readLine().toInt()
        cntArr[numIndex]++
    }

    var cnt: Int = 0
    val bufferWriter = System.out.bufferedWriter()

    for (i in 1 until maxSize) {
        cnt = cntArr[i]
        for (j in 1..cnt) {
            //println(i+1)
            //bufferWriter.write("$i\n").toString()
            bufferWriter.write(i.toString())
            bufferWriter.write("\n")
        }
    }
    bufferWriter.flush()
    bufferWriter.close()
}