[알고리즘 문제풀이] 수 정렬하기3

문제 제목 : 수 정렬하기3

문제 난이도 : 하

문제 유형 : 정렬

https://www.acmicpc.net/problem/10989
시간 제한 : 5초
메모리 제한 : 8MB

문제풀이 아이디어

1. 데이터의 개수 최대 10,000,000개 -> python 기본정렬 알고리즘으로 풀 수 없다!!
2. 시간 복잡도 O(N)의 알고리즘 이용해야 한다.
3. 수의 범위가 1 ~ 10,000이므로 계수 정렬 이용
   

< 소스코드 >

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)