[백준] 10989번 - 수 정렬하기 3 (파이썬) (feat. 정렬하지 않고 정렬하기,,?)

1. 문제

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

(문제는 쉬우나 메모리 제한이 아주 빡센 문제이다.)

 

2. 코드

import sys

n = int(input())
l = [0 for i in range(10001)]
for i in range(n):
    l[int(sys.stdin.readline())] += 1

for i in range(10001):
    for j in range(l[i]):
        sys.stdout.write(str(i) + '\n')

 

3. 주요 포인트

이 문제는 메모리 공간 제한이 아주 심한 문제이다.

그냥 sort를 사용하면 바로 메모리초과 발생이다. 따라서 절대 sort를 해서는 안된다.

그렇다면 어떻게 sort를 하는가?

1~10000이 input 수의 범위이므로 10000개짜리 0으로 초기화된 list를 생성해서 input수를 index로 가지는 것을 +1 해준다.

그런 후에 10000까지 돌면서 그 수만큼 print를 해주면 된다.

이때, input()과 print() 대신 sys.stdin.readline()과 sys.stdout.write()를 사용하여 시간을 줄여준다.