[python] 백준 10989번 수 정렬하기 3, 계수 정렬 및 readline() 함수 적용.

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

10989번: 수 정렬하기 3

import sys
lst = [0] * 10001
N = int(sys.stdin.readline())
for _ in range(N):
    lst[int(sys.stdin.readline())] += 1

cnt = 0
for i in range(10001):
    if lst[i] != 0:
        for _ in range(lst[i]):
            print(i)
            cnt += 1
        if cnt == N:
            exit(0)

입력 예시

10
5
2
3
1
4
2
3
5
1
7

출력 예시

1
1
2
2
3
3
4
5
5
7

일반적인 정렬 알고리즘 사용시 숫자가 많으면 속도가 느리기에

다이나믹 프로그래밍 기법으로 메모이제이션으로 리스트 index에 입력받은 수를 대입하여 1씩 더해주는 방법으로

출력시 for문을 돌려 입력 받은 개수 만큼 출력을 해준다.

또한 python 내장 함수인 input()은 속도가 느리므로

sys.stdin.readline()을 적용해준다.