728x90
🤖
문제
https://www.acmicpc.net/problem/10989
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
정렬을 사용하면 메모리 초과가 됩니다.
주어지는 수의 개수가 최대 1천만개로 이를 모두 저장해서 정렬한다면, 4바이트 * 1천만 = 40MB에 달하여 상당한 메모리를 차지한다고 볼 수 있습니다.
다만, 주어지는 수의 범위는 최대 1만까지이기 때문에 각각의 수를 인덱스로 하는 배열을 만들고 개수를 기록한 후 앞에서부터 하나씩 뽑아서 출력합니다.
(아래의 코드로 PyPy3에서는 메모리 초과, Python3에서는 통과)
728x90
'유물 > └ 백준' 카테고리의 다른 글
| <백준(파이썬)> 10815번: 숫자 카드 (0) | 2022.04.01 |
|---|---|
| <백준(파이썬)> 1715번: 카드 정렬하기 (0) | 2022.03.30 |
| <백준(파이썬)> 10828번: 스택 (0) | 2022.03.23 |
| <백준(파이썬)> 1068번: 트리 (0) | 2022.03.23 |
| <백준(node.js)> 1978번: 소수 찾기 (0) | 2022.02.22 |