백준 10989 : 수 정렬하기3(카운팅정렬)

수 정렬하기 3

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
5 초 (하단 참고)	8 MB (하단 참고)	143911	32743	24277	23.335%

문제

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

입력

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

출력

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

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 

1
1
2
2
3
3
4
5
5
7

---

코드

# https://teching.tistory.com/
import sys
# 계수정렬
countingNum = [0] * 10001
for _ in range(int(sys.stdin.readline().rstrip())):
    countingNum[int(sys.stdin.readline().rstrip())] += 1
for i in range(10001):
    for _ in range(countingNum[i]):
        print(i)

해설

메모리 제한이 8MB로 빡빡한 문제이다. 

계수 정렬을 구현해서 풀었다. 계수 정렬에 관한 내용은 https://teching.tistory.com/80에서 정리를 해두었다!

정렬 알고리즘 3 : 계수 정렬(Counting sort)

처음에는 입력값들을 리스트에 저장해서 세는 방법을 사용했는데 입력을 리스트에 저장하면 그 자체만으로 메모리 허용량을 초과해버린다. (최대 천만 개가 들어오기 때문에)

그래서 입력은 저장하지 않고 각 숫자가 몇 번 들어왔는지 세는 countingNum리스트만 저장을 했다.