<백준(파이썬)> 10989번: 수 정렬하기 3

 

🤖

 

문제

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

10989번: 수 정렬하기 3

 

풀이

정렬을 사용하면 메모리 초과가 됩니다.

주어지는 수의 개수가 최대 1천만개로 이를 모두 저장해서 정렬한다면, 4바이트 * 1천만 = 40MB에 달하여 상당한 메모리를 차지한다고 볼 수 있습니다.

다만, 주어지는 수의 범위는 최대 1만까지이기 때문에 각각의 수를 인덱스로 하는 배열을 만들고 개수를 기록한 후 앞에서부터 하나씩 뽑아서 출력합니다.

(아래의 코드로 PyPy3에서는 메모리 초과, Python3에서는 통과)