[BOJ 10989, Python 3] 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

풀이

메모리 제한이 많이 작습니다. 그런데 정렬할 수의 최댓값이 10,000이므로 크기가 10001인 배열을 만들고, 어떤 수 x가 있으면 arr[x] += 1을 해주어서 마지막에 출력할 때는 배열의 인덱스를 해당 위치의 리스트가 가지고 있는 값만큼 출력을 해주면 됩니다.

 

이런 정렬은 카운팅 소트(Counting sort)라고 부르며 자세한 내용은 https://00ad-8e71-00ff-055d.tistory.com/36 이 글을 참조하시면 됩니다.

 

 

코드

input = __import__('sys').stdin.readline
n = int(input())
arr = [0] * 10001
for i in range(n):
    x = int(input())
    arr[x] += 1
for i in range(10001):
    for j in range(arr[i]):
        print(i)