10989_수 정렬하기 3

문제는 더보기!

 

문제

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

입력

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

출력

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

예제 입력 1 복사

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 복사

1
1
2
2
3
3
4
5
5
7

똑같은 수 정렬하는 문제이지만, 메모리가 8MB만 주는것을 알 수 있다.

힌트는 들어오는 수는 천만개까지 엄청 많지만, 수는 1~10000 사이의 수만 들어온다는 것

그래서 나는 미리 10001개의 0이 들어있는 리스트를 만든 후에, 수가 들어오면 그에 해당하는 index값을 찾아 +1씩 하는 방식으로 쌓았다.

 

예를 들면, [0,0,0,0,0,0,0] 이런 데이터에서 3이들어오면

[0,0,1,0,0,0,0 ] 이런식으로 쌓이게끔 한후에, 리스트를 처음부터 그 숫자만큼 출력하게 만들었다.

 

import sys

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

i=0
for j in lst:
    for _ in range(j):
        print(i)
    i+=1