[BOJ] 10989번 : 수 정렬하기3

🔒 문제

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

⌨ 입력

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

🖨 출력

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

📚 예제

Ex1)

10
5
2
3
1
4
2
3
5
1
7

1
1
2
2
3
3
4
5
5
7

📌 풀이

처음에 sort함수 사용했는데 메모리 초과가 떴다.
그래서 구글링해보니 sort함수는 메모리 사용을 많이 한다고 한다.
그래서 계수 정렬을 이용했다.
계수 정렬은 주어지는 수의 범위가 작을때 사용하면 좋은 정렬로, 이 문제에서 자연수의 범위가 10000이하 이기 때문애
계수 정렬을 이용하여 문제를 풀었더니 풀렸다.

🔑 python 코드

import sys
N = int(sys.stdin.readline())
ary = [0]*10001

for i in range(N):
    data = int(sys.stdin.readline())
    ary[data]+=1 // 계수정렬 쓰려고

for i in range(10001):
    if(ary[i]!=0):
        for j in range(ary[i]):
            print(i)