[BOJ] 백준 10989 수 정렬하기 3 (Swift)

문제

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

10989번: 수 정렬하기 3

풀이

수가 최대 10,000,000개가 등장할 수 있습니다.
이는 $O(n)$, $O(n\log{n})$의 시간복잡도가 걸리는 정렬로는 풀이할 수 없습니다.

이 수는 10,00보다 작거나 같은 자연수라는 것에 힌트를 얻어 counting 정렬을 사용할 수 있습니다.

Swift에서는 입력(readLine)과 출력(print)이 백준에서 다른 언어에 비해 많이 느립니다.

출력을 문자열에 계속해서 더해주어 한 번만 출력하도록 구현하였습니다.

소스코드

후기

Counting sort에 대해 모른다면 시간초과가 발생하는 문제입니다.
꼭 알아두어야 할 정렬 방법인 것 같습니다.