[BOJ] #10989 - 수 정렬하기 3

10989번: 수 정렬하기 3

 

** 문제 유형

• 정렬

 

** 풀이

1. 데이터의 개수가 최대 10,000,000개
   • 파이썬 2초당 20,000,000개의 연산 수행
   • 파이썬의 기본 정렬 라이브러리 사용시, O(nlogn)
2. 수의 범위가 1 ~ 10,000 이므로 계수 정렬을 이용 -> O(n)
3. 데이터의 개수가 많을 때 파이썬에서 sys.stdin.readline() 사용 (input() 보다 빠름)

 

+) 계수 정렬 (Counting Sort) 알고리즘

• 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법
  • 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정
  • 데이터가 등장한 횟수를 카운트하여 배열에 저장
  • 데이터의 개수(배열의 값)만큼 인덱스를 출력

 

import sys

n = int(sys.stdin.readline())

array = [0] * 10001

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