[Python] 백준 10989번 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

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

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

풀이

import sys

input = sys.stdin.readline
N = int(input())
   
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * 10001

# 각 데이터에 해당하는 인덱스의 값 증가
for i in range(N):
    count[int(input())] += 1
    
# 리스트에 기록된 정렬 정보 확인
for i in range(1, 10001):
    while count[i]:
        print(i)
        count[i] -= 1

 

짚고 넘어가야 할 부분❗❗

다음과 같이 수 정렬하기 2 문제와 되게 유사하다라는 걸 확인할 수 있다.

하지만 같은 답안을 제출할 경우 메모리 초과 오답 판정을 받게 된다. 메모리 제한 크기가 다르기 때문이다.

수 정렬하기 3 문제의 경우 데이터의 크기가 10000보다 작거나 같은 자연수로 한정되어 있고,

데이터의 크기가 많이 중복되어 있어 계수 정렬을 이용하여 푸는게 적절하다.

계수 정렬의 공간 복잡도는 O(N + K)이다.

https://leeseong010.tistory.com/29

[Python] 백준 2751번 수 정렬하기 2