[백준] 10989번 수 정렬하기3

문제 설명

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

제한 사항

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

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

​

입출력 예

input	output
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

접근법

이번 문제는 수 정렬하기2 보다 메모리를 적게 사용해야합니다. 기존의 수 정렬하기 1,2 같은 경우에는 모든 수를 다 저장했었는데요, 최대 천만개의 수를 리스트에 다 저장해 버린다면, 8MB를 훌쩍 넘을 것 입니다. 여기서 계수 정렬의 원리 중, 인덱스를 카운트 하는 방법을 생각했습니다. 숫자의 범위는 최대 10000보다 작은 자연수기 때문에, 10000길이를 가지는 리스트를 0으로 초기화해주고, 입력받는 수의 인덱스에 1씩 더해가면 됩니다. 출력할 때는 리스트 내에서 0을 가지는 인덱스는 뛰어 넘고, 0 이상인 인덱스만 그 수만큼 출력해 주시면 됩니다.

​

나의 코드

import sys

number = int(input())
number_list = [0] * 10001

for _ in range(number):
    number_list[int(sys.stdin.readline())] += 1

for index, item in enumerate(number_list):
    if item != 0:
        for it in range(item):
            sys.stdout.write(str(index)+'\n')