[Baekjoon] 10989. 수 정렬하기 3 ( 계수 정렬 )

# Problem

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

# My Answer - 시간 초과

n = int(input())
result=[]
for i in range(n):
    result.append(int(input()))
result.sort()
for i in result:
    print(i)

 

# Solution 1 - 계수 정렬

import sys

n = int(sys.stdin.readline())
array = [0] * 10001

for i in range(n):
    data = int(sys.stdin.readline()) 
    array[data] += 1
    
for i in range(10001):
    if array[i] != 0:
        for j in range(array[i]):
            print(i)

파이썬에서 데이터의 개수가 많을 때는 파이썬에서는 sys.stdin.readline()을 사용

---

# 계수 정렬 (Counting Sort)

수의 범위가 작을 때 사용 (1~10,000)

배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬방법

배열의 크기는 데이터의 범위를 포함할 수 있도록 설정

데이터가 등장한 횟수 count