10989 수 정렬하기3

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

# 이 문제는 계수정렬 문제이다.
# 특정한 조건 하에서만 아주 효율적으로 작동한다.
import sys
read = sys.stdin.readline

N = int(read())

array = [0] * 10001
for j in range(N):
    array[int(read())] += 1

for i in range(10001):
    if array[i] != 0 :
        # 0이 아니면 입력받을 때 해당 숫자가 나왔었다는 것을 의미
        for k in range(array[i]):
            print(i)

3. 문제 풀이

이 문제는 전형적인 계수정렬이다. 극한의 메모리를 사용하기 때문인데, 사실 계수 정렬은 특정한 조건하에서만 굉장히 효율적으로 작동한다. 예를 들어, 같은 수가 많이 반복되며 숫자들이 연속적일수록 좋다. 극히 안좋은 예는 0,55555,1111111 이렇게 들어오는 예제이다.

코딩자체는 어렵지 않다. 입력으로 들어오는 수를 index로 사용해 해당하는 array의 count를 올려준다. 그리고 이를 다시 출력 for문에서 count가 있는지 없는지를 판단하기위해 사용하고, count가 있는 경우엔 해당 index를 count만큼 출력하면 된다.