What I Learned/Algorithm Practice

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

Interrobang 2022. 9. 27. 18:30

<문제 링크>

 

10989번: 수 정렬하기 3

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

www.acmicpc.net

 

<문제 풀이>

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, 계수 정렬)을 사용한다.