[백준 / 파이썬] 10989번 수 정렬하기3

import sys
n = int(sys.stdin.readline())
a = [0]*10001

for i in range(n):
    d = int(sys.stdin.readline())
    a[d] += 1
for i in range(10001):
    if a[i] != 0:
        for j in range(a[i]):
            print(i)

list에 새로운 값을 append 해서 푸는 방식을 사용하려 했지만 append를 하게 되면 메모리 재할당이 일어나 메모리를 많이 잡아먹는다고 한다

수의 범위가 1~10,000 이므로 계수 정렬 이용

계수 정렬 알고리즘

- 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법

- 배열 크기는 데이터 범위 포함할 수 있게 설정

- 데이터가 등장한 횟수 센다

- 데이터의 개수가 많을 때 파이썬에서는 sys.stdin.readline() 사용

 

만약 [2, 2, 4] 라면 2의 인덱스는 2, 4의 인덱스는 1

앞에서부터 진행해 수가 하나씩 나올 때마다 인덱스 증가

 

입력받는 값이 10,000까지 이기 때문에 10001까지 0으로 초기화된 배열 생성

입력받을 때마다 그 수에 해당하는 인덱스에 +1 해서 그 수의 개수를 담는다

배열을 돌면서 값이 0이 아니면 값만큼 인덱스에 해당하는 숫자 출력하는 방식으로 자동 정렬되도록