백준 10989번: 수 정렬하기 3

백준 10989번: 수 정렬하기 3

아이디어

입력의 개수가 천만개다. 그냥 sort()하려고 하면 메모리 초과가 난다. 하지만 숫자의 최댓값이 10000이다. 이것을 잘 이용해보자.

10001개짜리 배열을 만들고, 0으로 꽉 채운다. a라는 숫자가 입력됐을 때, a번째 인덱스에 위치한 값을 1 더해준다.

0보다 큰 값이 저장돼 있는 경우, 해당 인덱스에 해당하는 숫자가 입력됐다는 뜻이다. 저장된 값만큼 여러번 출력해주도록 하자.

코드

import sys
input = sys.stdin.readline
N = int(input().rstrip())
cSort = [0]*10001

while N > 0:
    num = int(input().rstrip())
    cSort[num] += 1
    N -= 1

for i in range(10001):
    if cSort[i] > 0:
        cnt = cSort[i]
        while cnt > 0:
            print(i)
            cnt -= 1

여담

일반적인 방법으로 input을 하면 시간초과가 난다. 따라서 sys.stdin.readline으로 입력을 받도록 하자.