[백준 - python] 10989번: 수 정렬하기 3

<문제 링크>

10989번: 수 정렬하기 3

 

<문제 풀이>

import sys

N = int(sys.stdin.readline())
num_list = [0] * 10001

for i in range(N):
    num = int(sys.stdin.readline())
    num_list[num] += 1

for i in range(10001):
    if num_list[i] != 0:
        for j in range(num_list[i]):
            print(i)

10989 입출력 예시

*key point: 2750, 2751번 문제와 유사하나 다루는 수의 범위가 다르기 때문에 같은 방법으로 문제를 풀 경우 시간 초과와 메모리 부족이 발생한다. 이를 해결하기 위해서 특정 상황(제한된 작은 범위, 양의 정수)에서 빠른 속도를 가지면서 메모리 또한 효율적으로 사용할 수 있는 카운팅 정렬(Counting sort, 계수 정렬)을 사용한다.