[백준 10989번-파이썬/Python] 수 정렬하기 3

http://acmicpc.net/problem/10989

{코드}

import sys
def input():
	return int(sys.stdin.readline())
def print(v):
	sys.stdout.write(str(v)+'\n')
data = [0]*10001
for _ in range(input()):
	data[input()] += 1
for i in range(1, 10001):
	if data[i]:
		for _ in range(data[i]):
			print(i)

{설명}

이 문제는 주어지는 수의 개수가 너무 많기 때문에 O(nlogn)으로도 시간 초과가 나게 됩니다.

그러나 수의 범위가 1에서 10000이므로 계수 정렬을 사용할 수 있습니다.

계수 정렬은 범위가 양의 정수일때 최댓값까지를 인덱스로 가진 리스트를 만들어 각 수가 몇 개인지 파악하는 정렬입니다.

시간 복잡도는 데이터 개수가 n, 최댓값이 k일 때 O(n+k)입니다.