[백준] 10989 - 수 정렬하기 3(python)

문제링크

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

문제

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

입력

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

출력

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

 

풀이코드

import sys

n_list = [0]*10001
for _ in range(int(sys.stdin.readline())):
    n_list[int(sys.stdin.readline())] += 1
for i in range(len(n_list)):
    if n_list[i] != 0:
        for _ in range(n_list[i]):
            sys.stdout.write(str(i)+'\n')

이번 문제가 참 어려운게 메모리 제한 때문인 것 같다.

보통 이런 정렬 문제는 시간 초과가 문제인 경우가 많은데

이 문제는 메모리 제한도 5MB로 제한되어 있어서 더 풀기 어려웠던거 같다.

 

그래서 해당 문제는 풀이 방법을 구글링해서 푼 결과,

사전에 n의 범위로 주어지는 부분을 리스트로 구현해두고 

리스트에서 필요한 부분만 값을 변경해 준 뒤 출력하는 방식이다.

 

이번에는 실행 시간을 최소화 하기 위해서 출력 방식도 sys.stdout으로 바꾸었는데

그냥 print문을 썼을때가 시간이 더 빠르게 나온다 왜그런거지....