[백준 문제풀이] 10989 - 수 정렬하기 3

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

문제

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

입력

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

출력

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

풀이

파이썬은 다른 메이저 프로그래밍 언어들에 비해 무거운 편이다. 그래서 이런 백준 문제풀이에 시간 제한이나 메모리 제한이 걸릴 때 좀 더 신경써서 풀이를 해야한다(물론 문자열 처리나 편의성이 남다르긴하다).

일반적으로 사용하는 input()과 print()함수 또한 무거운 편이라, sys 모듈에 있는 sys.stdin.readline과 sys.stdout.write를 사용해 속도를 높힐 수 있다. 그리고 범위는 1 ≤ N ≤ 10,000,000 이지만 수가 10,000 이므로 카운팅정렬을 이용해 제한시간 내에 코드를 풀 수 있다.

import sys

input = sys.stdin.readline
print = sys.stdout.write

N = int(input().rstrip())

Counting = [0] * 10001  # 카운팅 정렬, 범위가 1 <= X <= 10000 이므로 10001의 크기를 가진 배열을 0으로 초기화

for _ in range(N):
    s = int(input().rstrip())
    Counting[s] += 1

for i in range(10001):
    if Counting[i] != 0:
        for j in range(Counting[i]):
            print("".join(str(i)) + "\n")