10989번: 수 정렬하기 3

문제

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

입력

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

출력

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

이 문제에는 8MB의 메모리 제한이 있다. 그래도 저번에 짰던 코드를 넣어보았는데 역시나^^ 메모리 초과로 실패했다. 메모리를 줄일 방법이 어떤 게 있을지 생각해봤는데 일단 배열을 저장해서 sort할 수 없다는 것에 주목해보았다.

10,000,000개의 숫자를 모두 저장하면 당연히 메모리 초과가 뜰 테니 1~10,000까지라 생각한 배열을 만들어 준 후 각 list 원소의 index + 1의 수가 몇 개 들어있는지 세면 되지 않을까 하는 생각에서 코드를 다시 작성해보았다.

알고리즘을 제대로 공부하는 게 처음이라 나름 획기적인 것 같다고 생각하며 다른 사람들 코드 보러 들어갔더니 다 코드가 비슷해서... 원래 이렇게 푸는거구나 했다...

그래서 아래와 같은 코드가 나왔다. 결과는 통과! 나름, 뿌듯했다 :-)

import sys

n = int(sys.stdin.readline())

data = [0 for _ in range(0,10001)]

for i in range(0, n):
    num = int(sys.stdin.readline())
    data[num - 1] += 1

for i in range(len(data)):
    for j in range(0, data[i]):
        print(i + 1)