[BOJ/Python] 10989 - 수 정렬하기 3

시간 제한 3초, 메모리 제한 8MB인 수 정렬하기 문제다.

당연히 sort 라이브러리를 쓰면 메모리 제한이 걸린다. 파이썬은 시간 제한 문제가 역시 빡세다...

# 입력받은 모든 값을 저장하면 안된다는 결론.
# 미리 결과값 리스트를 만든다
# 성공! 그런데 9336ms 걸리는게 맞는건가? 다른 사람들 것 보니까 비슷한듯. 역시 파이썬은 속도가 쫌...
from sys import stdin
n = int(stdin.readline())

arr = [0]*10000

for i in range(n):
    # 입력받은 값이 3이면 음... 딱 떨어지게 1만 배열 만들고 싶으니 인덱스를 하나 줄이는 걸로(3 입력받으면 2 인덱스 1 추가)
    arr[int(stdin.readline())-1]+=1

for i in range(len(arr)):
    # 1부터 시작했을 때, 입력받은 값의 수만큼 해당 숫자 출력하기
    if arr[i] != 0:
        for j in range(arr[i]):
            print(i+1)

풀이

입력받은 수 자체를 배열에 append하는 것이 아니라,

문제 조건에 맞게 1부터 10,000까지의 빈 배열을 만들어 두고 (기본값 0) 입력값에 해당하는 인덱스의 값을 1씩 올린다.

Ex) 3을 입력받으면 인덱스 2의 값을 1 올린다. [0,0,(+1)....]

그리고 2중 for문을 돌려서 해당 인덱스의 값 만큼 해당 수를 반복해서 출력시킨다.

다른 문제에도 써먹을 듯하다.