[백준] 10989 수 정렬하기 3

문제출처] https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

---

문제요약

시간 제한과 메모리 제한이 있어 Counting Sort를 이용해 정렬을 수행하는 문제

풀이

카운팅 정렬(계수 정렬)은 데이터 셋이 특정한 범위로 제한되어 있을 때 속도를 높일 수 있는 정렬 방식이다.

데이터를 인덱스로 가지는 배열에 카운트를 1씩 증가시키는 방식으로 정렬이 수행된다.

input() 을 이용할 때보다 sys.stdin.readline() 을 이용할 때 수행 속도가 향상된다.

---

소스코드는 Python 3으로 작성되었습니다.

import sys
input = sys.stdin.readline

n = int(input())
arr = [0 for i in range(10001)]

for _ in range(n):
  arr[int(input())] += 1

for i in range(1,10001):
  for _ in range(arr[i]):
    print(i)