[CodingTest] BOJ 10989 - 수 정렬하기 3(Python)

BOJ 10989 - 수 정렬하기 3(Python)

• 문제 링크: https://www.acmicpc.net/problem/10989
• 시간 제한: 3초
• 메모리 제한: 8MB

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

메모리 제한이 큰 편이 아니다.
입력된 수를 전부 메모리에 저장하여 sorting 하는 방식의 접근은 메모리 초과가 발생한다.
(ex. 리스트에 입력된 수를 전부 추가한 뒤 sorting)

이러한 메모리 문재를 해결하기 위해서 다음의 접근을 하였다.

1. 각 숫자의 입력 횟수를 defaultdict를 활용하여 카운트
2. count 횟수가 0이 아닌 숫자에 대해서만 count된 횟수만큼 출력

이러한 접근법은 Counting sort(계수 정렬)이라고 한다.

Solution (Python)

import sys
from collections import defaultdict


input = sys.stdin.readline

N = int(input())
n_cnt = defaultdict(int)
for _ in range(N):
    n_cnt[int(input())] += 1

for n in range(10000+1):  # 입력되는 수는 10,000보다 작거나 같은 자연수이다.
    print(f'{n}\n' * n_cnt[n], end='')