계수정렬: 10989

백준 10989번 문제...
후;; 쉽지않네 ;;;;

• 계수정렬이란?
  비교 기반의 정렬 알고리즘이 아니라, 정수나 정수로 표현 가능한 자료에 대해서 동작하는 선형 시간 정렬 알고리즘이다.
  특정 조건에서 매우 효율적으로 동작한다.

  조건1: 정수 또는 정수로 표현 가능한 자료에만 적용가능
  조건2: 데이터의 범위가 너무 크지 않을 것(전체 정렬해야하는 데이터의 값의 범위가 아니라, 정렬해야하는 데이터 요소 값의 범위.
  예컨데 100만의 데이터 갯수는 괜찮지만, 100만까지의 요소값 범위면 조금 곤란!

해당 알고리즘의 원리는 다음과 같다.
1. 카운팅 단계
입력 배열의 각 원소의 출현 횟수를 세어서 별도의 카운트 배열에 저장한다.
2. 누적합 계산
카운트 배열의 각 원소를 누적 합으로 변환한다.
3. 결과 배열 생성
원본 배열을 뒤에서부터 순회하며, 각 원소의 올바른 위치를 카운트 배열에서 찾아 결과 배열에 배치한다.

• 나의 풀이

import sys

N = int(input())
count = [0]*10001

for i in range(1, N+1):
    temp = int(sys.stdin.readline().strip())
    count[temp] += 1
    
for num in range(10001):
    if count[num] > 0:
        for _ in range(count[num]):
            print(num)