BOJ 10989번 수 정렬하기3 파이썬

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

풀이 방식

수 정렬하기 2에서는 nlogn의 속도를 가진 Heap 정렬을 사용했었지만, 수 정렬하기 3에서도 똑같이 적용하면 메모리 초과가 난다.

수 정렬하기 2는 메모리 제한이 256MB이었던것에 비해, 3에서는 8MB밖에 주어지지 않기 때문.

위 사진을 참고해보면, 사이즈가 10,000,000인 배열은 무려 40MB의 메모리나 사용한다는 것을 알 수 있다.

이 문제의 핵심은 “이 수는 10,000보다 작거나 같은 자연수이다.”이다.

즉, 어차피 입력받는 숫자는 10,000 이하이기 때문에, 10,000 사이즈의 배열을 만들어두고,

배열의 ‘값’을 배열 ‘인덱스’(특정 숫자)의 등장횟수로 생각해서 숫자를 입력받을때마다, 해당 인덱스의 값을 +1 해주면 된다.

그리고 범위 제한 한정 log(N)의 속도를 가진 매우 빠른 알고리즘인 계수 정렬 (Counting Sort)를 사용해서 문제를 풀어주면 된다.

import sys
input = sys.stdin.readline

n = int(input())
arr = [0]*10001

for _ in range(n):
    v = int(input())
    arr[v]+=1

for i,v in enumerate(arr):
    for j in range(v):
        print(i)