문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
예제 입력
10
5
2
3
1
4
2
3
5
1
7
예제 출력
1
1
2
2
3
3
4
5
5
7
위 문제는 이전 수 정렬하기1,2와는 다르게 시간제한 5초, 메모리 제한이 8MB입니다. 위 문제를 해결하고자 이전에 2에서 푼 코드를 그대로 대입해보기도하고 해쉬를 구현해서도 해결해보려고도 해봤지만 시간제한에서 막히거나 메모리초과 에러가 발생했습니다.
입력값을 받은 것을 sort 함수를 사용할 때 퀵정렬을 하게 되는데 그 부분에서 메모리 또는 시간 초과를 발생시키는 것으로 생각되었습니다
그래서 생각한 방법은 수는 10000개가 최대이므로 미리 모든 10000까지의 인덱스를 미리 선언해주고 들어온 입력값을 인덱스로 해당하는 값에 입력된 횟수를 담아주고 이후에 for 문으로 돌면서 해당하는 횟수만큼 해당 인덱스를 출력해주는 방법을 생각했습니다
처음에 해결되지 않아서 막히는 부분들이 있을때 침착하게 다른 방법을 생각해보는 것이 필요합니다.
시간초과 문제가 있는지라 입력값은 최대한 빠르게 받을 수 있도록 sys 모듈을 사용합니다
import sys
#정상 작동 코드
N = int(input())
nums = [0] * 10001
for _ in range(N):
num = int(sys.stdin.readline().strip())
nums[num] += 1
for _ in range(10001):
if nums[_] != 0:
for i in range(nums[_]):
print(_)
