문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
예제
나의 풀이
import sys
N = int(sys.stdin.readline())
num_list = []
for _ in range(N):
num_list.append(int(sys.stdin.readline()))
print(*sorted(num_list), sep='\n')- `N`의 최댓값이 `10,000`이기 때문에 빠른 실행을 위해 `sys.stdin.readline()`을 사용했다.
- 결과 출력을 위해 언패킹 연산자를 사용했다.
- 하지만 이것은 메모리 초과로 실패한 풀이다.
다른 사람의 풀이
import sys
N = int(sys.stdin.readline())
num_list = [0] * 100001
for _ in range(N):
num_list[int(sys.stdin.readline())] += 1
for i in range(100001):
if num_list[i] != 0:
for _ in range(num_list[i]):
print(i)- for문에서 `append()`를 사용하면 매 단계마다 메모리 재할당이 일어나기 때문에 속도 저하가 발생해서 메모리를 효율적으로 사용하지 못한다.
- 이 경우에는 입력값의 최댓값을 길이로 가지는 리스트를 먼저 선언하고, 리스트 내의 각 요소가 몇 번 등장하는지 세어서 정렬하는 계수정렬 방식을 사용하는 것이 더욱 효율적이다.
- `N`의 최댓값인 `10,000+1`을 길이로 가지는 리스트를 선언한다. 인덱스가 `0`부터 시작하기 때문에 편의상 `1`을 더했다.
- 입력값을 받을 때마다 리스트의 해당 인덱스 값에 `1`을 더한다.
- 최종적으로 리스트의 해당 인덱스의 값만큼 인덱스를 출력한다.