728x90
https://www.acmicpc.net/problem/10989
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
728x90
예제 입력 1
10
5
2
3
1
4
2
3
5
1
7
예제 출력 1
1
1
2
2
3
3
4
5
5
7
'수 정렬하기 2' 와의 차이
'수 정렬하기 2' 문제는 시간 제한 2초, 메모리 제한 256MB
이다. 즉, 메모리는 넉넉하게 주고 최대한 빠르게 정렬해야 하는 문제이다.
반면, 이 문제는 시간 제한 5초, 메모리 제한 8MB
이다. '수 정렬하기 2' 문제와 다르게 시간은 넉넉하게 주되, 메모리는 적게 사용해야 한다.
따라서 '수 정렬하기 2'에서 썼던 방식인 sorted 함수를 사용하거나 merge sort 방법을 사용하는 것은 list를 무수히 만들어 정렬하는 방법이기 때문에 메모리 초과가 발생한다.
때문에 시간은 많이 걸리더라도 메모리를 절약할 수 있는 방법을 사용해야 한다.
import sys
N = int(sys.stdin.readline())
arr = [0] * 10001
for _ in range(N):
arr[int(sys.stdin.readline())] += 1
for num in range(10001):
if arr[num] != 0:
for _ in range(arr[num]):
print(num)
메모리 초과
import sys
N = int(sys.stdin.readline())
arr = [int(sys.stdin.readline()) for _ in range(N)]
sorted_arr = sorted(arr)
for num in sorted_arr:
print(num)
728x90
'Problem Solving > BOJ' 카테고리의 다른 글
[백준, BOJ 2530] 인공지능 시계 (python) (0) | 2021.12.13 |
---|---|
[백준, BOJ 2525] 오븐 시계 (python) (0) | 2021.12.13 |
[백준, BOJ 2480] 주사위 세개 (python) (0) | 2021.12.11 |
[백준, BOJ 2420] 사파리월드 (python) (0) | 2021.12.11 |
[백준, BOJ 1297] TV 크기 (python) (0) | 2021.12.11 |