[백준/Kotlin] 10989번: 수 정렬하기 3

문제

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

입력

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

출력

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

예제

예제 입력 1	예제 출력1
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

 

풀이

이 문제를 총 3가지 방식으로 풀어보았다.

 

• 크기가 n인 배열에 모든 숫자를 차례대로 넣은 후 정렬하여 출력
• Map을 사용하여 입력으로 들어오는 숫자들과 그 개수만 저장한 후 정렬하여 출력
• 크기가 10001인 배열에 각 숫자마다 개수를 저장한 후 차례대로 출력

그 중 실행 시간이 가장 짧은 세 번째 방식에 대해 설명해보겠다.

 

1. 1부터 10000까지의 숫자가 등장할 수 있기 때문에 크기가 10001인 배열을 선언한다.
2. 입력으로 들어오는 숫자의 값을 index로 하는 배열의 값을 하나씩 증가시킨다.
3. 배열의 index 1부터 10000까지 확인하며 해당 숫자가 등장한 개수만큼 출력한다.

 

마지막 출력 부분을 처음에는 StringBuilder를 사용하여 append하는 방식으로 풀었는데 메모리 초과가 발생해서 BufferedWriter를 사용하여 write하는 방식으로 풀어야 했다.

 

전체 소스코드는 다음과 같다.

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

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()

    // 배열 초기화
    val list = IntArray(10001)

    // 나타난 숫자 표시
    for (i in 0 until n) {
        list[br.readLine().toInt()]++
    }

    for (i in 1..10000) {
        bw.write("$i\n".repeat(list[i]))
    }

    bw.flush()
    bw.close()
    br.close()
}