수 정렬하기 3

• 그냥 입력받고 정렬하고 출력하면 되는 문제이긴 한데.. 카운팅 소트를 써야만 하는 문제이다.
• n제한이 백만이었던 수 정렬하기 2에서도 카운팅 소트로 구현한 코드가 살짝 더 빠르게 돌아가는걸 보긴 했었는데, 이문제는 n 제한이 10배로 늘었고.. 그리고 무엇보다도 메모리 제한이 걸려서 모든 수를 다 메모리에 읽어 들이는 것이 불가능하다. 수의 범위가 10000 이하이므로 크기 10000짜리 배열에 각 숫의 등장 횟수를 저장하면 된다
• 출력해야 할 라인도 천만라인이기때문에, 출력을 최적화 하는 것이 큰 영향을 미친다. 그러나 출력을 최적화하는 방식인, 문자열에 출력할 내용을 모두 저장해놓고 한번에 출력하는 것은, 메모리 제한때문에 역시 불가능하다. 그냥 한줄씩 출력해도 통과하는데에는 별 문제는 없다. 빠른 코드들은 한줄씩 출력하는 대신, X줄씩 버퍼용 문자열에 저장해놓고 버퍼만큼씩 한번에 출력하는 방식으로 속도를 높였다. 하지만, 그렇게까지 귀찮게는 하기 싫을때 쓸 수 있는 함수로 sys.stdout.writelines가 있다. 얘는 문자열의 이터레이터를 인자로 받아서 출력해주는데, 긴 문자열 하나로 만들어서 print로 출력한것보다는 약간 느리지만 그래도 줄 수만큼 print를 호출해서 출력하는 것보다는 훨씬 빠르게 출력해준다. 평소에는 굳이 귀찮게 이런 함수를 쓸일이 없지만, 이 문제의 경우에는 이터레이터를 사용해서 메모리를 아끼면서도 빠르게 출력이 가능하다.

"""Solution code for "BOJ 10989. 수 정렬하기 3".

- Problem link: https://www.acmicpc.net/problem/10989
- Solution link: http://www.teferi.net/ps/problems/boj/10989
"""

import itertools
import sys

MAX = 10000


def main():
    N = int(sys.stdin.readline())
    count_by_num = [0] * (MAX + 1)
    for _ in range(N):
        num = int(sys.stdin.readline())
        count_by_num[num] += 1    
    sys.stdout.writelines(
        itertools.chain.from_iterable(
            itertools.repeat(f'{num}\n', count)
            for num, count in enumerate(count_by_num)
            if count > 0))


if __name__ == '__main__':
    main()