[Python]정렬 백준 10989

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 

이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

이번엔 수에 제한이 걸려있다.

10000보다 작거나 같은 자연수 중복된 수가 굉장히 많이 반복될것이다.

기수정렬과 카운팅정렬을 이용할수 있는데 기수정렬의 경우문제에서 준 메모리의 양으로는 부족하다.

기수정렬의 경우 버킷을 이용하는데  1000만개의 숫자를 배열에 담는데만 40MB가 사용된다. 10000이하면 하나의 인자당

약 2byte(2^14~2^15bit)정도가 최소로 잡아도 20MB가 사용되는데 주어진 메모리는 8MB이다.

주어진 숫자를 배열에 바로 저장하는거 조차 할수없다. 여기서 할수 있는 방법은 카운팅정렬이다.

해당숫자의 개수를 배열에 저장해 주는것이다.

크기 1만의 1차원 배열을 만들고 숫자를 받을때마다 해당 인덱스의 값을 1씩 늘려주면 된다. 메모리는 4Byte*10000이고 정렬속도는

들어올때마다 바로 정렬이 되므로 O(n)이다. 

이러한 제한적인 조건에서는 최고의 효율과 메모리 사용량을 보여준다.

import sys
 
n=int(sys.stdin.readline())
 
num_list=[]
result_list=[0 for _ in range(10001)]   #받을수의 최대값에 따라 배열을 만든다.
 
for i in range(n):  #받을때마다 해당인덱스에 넣어준다.
   result_list[int(sys.stdin.readline())]+=1
 
 
for i in range(len(result_list)):
    for j in range(result_list[i]):
        print(i)

코드 또한 매우 간결한것을 볼수있다.

메모리의 제한이 없다면 기수정렬도 가능할것이다.

아마 이번 정렬파트에서 한번쯤 다룰거 같다.