10989번 수 정렬하기 3

수 정렬하기 3

풀이

일반적으로 C언어 등에서는 정수 한 개를 저장하는 데 byte를 사용합니다. 개의 정수를 저장하려면 byte = MB가 필요합니다. 따라서 정수를 모두 담고 정렬하는 방식을 사용하면 메모리 초과를 받습니다.

이 문제는 계수 정렬(Counting Sort)이라는 방법을 이용해 해결할 수 있습니다. 이 문제에서는 입력으로 들어오는 정수의 최댓값이 작으므로, 부터 까지 몇 개의 수가 입력으로 들어왔는지를 저장하고 다시 부터 까지 입력으로 들어온 개수만큼 순서대로 출력해주면 됩니다.

이 방법을 사용하면 개의 정수만 사용해도 되므로 메모리를 절약할 수 있습니다.

def main():
    count = [0] * 10001
 
    N = int(input())
    for _ in range(N):
        number = int(input())
        count[number] += 1
 
    for i in range(1, 10001):
        for _ in range(count[i]):
            print(i)
 
 
main()