[백준] 수 정렬하기 3 (Python)

✏️ 문제

10989번: 수 정렬하기 3

✏️ 풀이

입력의 개수가 매우 많은 것에 비해 메모리 제한이 작은 문제이다.

따라서 입력을 모두 저장해서 sort()를 하면 당연하게도 메모리 초과가 난다.

따라서, Counting Sort를 일부? 이용하여,

10001 크기의 배열을 미리 만들어, 각 수의 출현 빈도수를 해당 인덱스에 저장한다.

그 후 반복문으로 배열을 차례대로 돌면서 빈도수만큼 출력해준다.

추가적으로, 이 문제처럼 입력이 매우 많은 경우 input() 대신 sys.stdin.readline을 써주는 것이 시간복잡도 면에서 좋다.

✏️ 코드

import sys

n = int(input())
table = [0] * 10001 # 0부터 10000 까지 개수 세어서 저장할 배열

for _ in range(n):
    table[int(sys.stdin.readline())] += 1
    
for i in range(10001):
    if table[i]==0:
        continue
    elif table[i]==1:
        sys.stdout.write(str(i)+'\n')
    else:
        for x in range(table[i]):
            sys.stdout.write(str(i)+'\n')