[Python] 10989 - 수 정렬하기 3

풀이

입력 받을 수 있는 수의 갯수는 천 만개 이고, 입력 받는 수는 1 ~ 10000까지의 수이다.

만약 배열을 이용해 모든 수를 저장하고 그들을 정렬한다고 한다면? 8MB의 메모리로는 절때 불가능 하다.

따라서 우리는 다른 방법을 생각해보아야 한다.

문제의 핵심은 다음과 같다.

1. 입력받는 수의 범위는 1 ~ 10000이다. 천 만개의 수를 모두 배열에 저장하여 정렬하는 것이 아닌, 1 ~ 10000까지 저장된 배열을 활용하여 문제를 해결하는 것이 메모리 사용에 효율적이다.
2. 배열의 크기가 10001인 배열의 인덱스는 0 ~ 10000번 까지 존재. 그 중, 0번 인덱스를 제외한 나머지 1 ~ 10000번 인덱스를 활용해보자.
3. 입력 받은 수는 배열의 인덱스 번호가 될 것이고, 이를 +1 하면 해당 인덱스 번호를 출력할 횟수가 된다.

# 10989 수 정렬하기 3

import sys

n = int(sys.stdin.readline().rstrip())

count = [0] * 10001 # 0 ~ 10000 까지의 인덱스 번호를 가지는 배열
for i in range(n):
    num = int(sys.stdin.readline().rstrip())
    count[num] += 1 # 입력 받은 숫자에 해당하는 인덱스를 증가시킴

for j in range(len(count)):
    if (count[j] > 0): # 앞서 입력 받은 인덱스만 추림
        for k in range(count[j]): # 몇 번 출력할 것인가
            print(j)