https://www.acmicpc.net/problem/10989
카운팅 정렬(Counting Sort, 계수 정렬) - 주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘, 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.
이번에는 기존방식 사용시 메모리 초과가 뜨게 된다. 공간복잡도를 줄이는 형식으로 풀어야 하는 문제.
내 제출
import sys
n = int(sys.stdin.readline())
num_list = [0] * 10001 # index가 0부터 시작이므로 10001개 생성
for _ in range(n):
num_list[int(sys.stdin.readline())] += 1 # 배열마다 각 숫자가 들어감
for i in range(10001):
if num_list[i] != 0:
for j in range(num_list[i]):
print(i)