[BOJ] 10989. 수 정렬하기 3

수 정렬하기 3 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초 (하단 참고)	8 MB (하단 참고)	71932	15650	11727	22.880%

문제

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

풀이

언뜻 보면 굉장히 쉬운 문제 같지만 메모리 제한이 있기 때문에, list에 입력 받은 수를 넣고 sort() 메서드를 사용하는 방식으로는 풀 수 없다. 

숫자를 저장하는 과정에서 문제가 생기므로, 그대로 저장하지 않는 방법을 사용해야 할 것 같았다. 입력하는 수의 크기가 10,000보다 작은 자연수 이므로 10000크기의 0으로 구성된 리스트를 만들어 해당 인덱스를 늘려주는 방식을 택했다.

#10989 수 정렬하기3 import sys n = int(sys.stdin.readline()) arr = [0]*10001 for i in range(n):   t = int(sys.stdin.readline())   arr[t] +=1 for i in range(1,len(arr)):   if arr[i]!=0:     for j in range(arr[i]):       print(i)

cs