[백준 10989] 수 정렬하기 3 with 파이썬

요구사항

 N(1 ≤ N ≤ 10,000,000)개의 숫자를 정렬하라

참고

1. 정렬의 하한은 NlonN 이다

-> 정렬로 구성할 수 있는 결정트리를 만들게 되면 리프 노드의 개수가 logN! = NlonN인 결정 트리를 만들 수 있다

-> 그 중에 하나가 정렬된 상태이다

-> 그러므로 NlogN이 정렬이 하한이다

 

2. 10,000,000을 정렬의 하한을 적용시켜 보면 제한시간안에 문제를 풀 수 없다

->그러므로 정렬이 아닌 다른 방법으로 풀이를 진행하여야 한다

 

3. 주어진 숫자의 범위가 작으니깐 각 숫자가 몇번 나왔는지 출력한다

 

풀이

import sys 
input= sys.stdin.readline
n=int(input())
arr= list(range(10010))
#입력을 받을 때 마다 해당 arr을 하나 증가 시켜 줄 수 있도록 한다
for i in range(n):
    value = int(input())
    arr[value]+=1
#현재 수가 몇번 나왔는지 출력한다
for i in range(10001):
    for j in range(arr[i]):
        print(i)