백준 10989번_수 정렬하기 3 [python/파이썬] + Counting sort

# 메모리 초과가 난 코드

import sys
 
max_size = 10000 # 입력될 숫자의 최대 크기
 
test_case = int(input())
num_list = []
 
for case in range(test_case):
    num_list.append(int(sys.stdin.readline().strip()))
 
N = len(num_list)
count = [0]*(max_size+1) #0으로 초기화된 입력될 max_size+1 길이의 배열 count를 생성
count_sum = [0]*(max_size+1) #count_sum은 누적합을 저장하는 배열
for i in num_list:
    count[i] += 1
 
count_sum[0] = count[0] # 입력에 0이 있을 수 있으므로
for i in range(1, max_size + 1):
    count_sum[i] = count_sum[i - 1] + count[i]
 
sorted_list = [0]*(N+1)
for i in range(N-1, -1, -1):
    sorted_list[count_sum[num_list[i]]] = num_list[i]
    count_sum[num_list[i]] -= 1
 
for i in sorted_list[1:]:
    print(i)

 

 그러나 이 문제에서 요구되는 것은 속도가 아니라 공간의 효율성이다. 그렇기 때문에 위의 코드는 메모리 초과의 문제가 발생한다. 그 이유는 입력되는 숫자들을 모두 배열로 저장하고 정렬하는 과정에서 다시 정렬된 배열을 만들기 때문이다. 즉, 이 문제를 해결하기 위해선 숫자들을 배열로 저장하면 안 된다. 이를 해결하기 위해 Counting sort가 사용된다.

 

 

# 정답 코드

import sys
 
N = int(input()) # 입력 받을 수의 개수
 
max_size = 10000 # 입력되는 수의 최대 값이 10,000이기 때문
 
count = [0]*(max_size+1)
 
for case in range(N):
    num = int(sys.stdin.readline().strip())
    count[num] += 1
 
for i in range(1,max_size+1):
    if count[i] != 0:
        for j in range(count[i]):
            print(i)