[백준/Python] 10989 수 정렬하기 3

[백준/Python] 10989 수 정렬하기 3

풀이 코드 및 설명

import sys

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

for _ in range(n):
    num_list[int(sys.stdin.readline())] += 1 

for i in range(10001):
    if num_list[i] != 0:
        for j in range(num_list[i]):
            print(i)

처음엔 문제가 수 정렬하기 1, 2 와 같아 코드를 그대로 제출하였다.

import sys

n = int(sys.stdin.readline())
arr = []
for _ in range(n):
    arr.append(int(sys.stdin.readline()))

arr.sort()

for i in range(len(arr)):
    print(arr[i])

하지만, 메모리 초과 라는 처음보는 결과가 나오게 되었다.
문제를 자세히 보면 시간 제한, 메모리 제한이 있다.

왜 메모리 초과라는 결과가 나왔는지 찾아보았다.

for 반복문 내에서 arr.append()를 통해서 삽입하고 있다. 이는 append 호출 시 메모리 재할당이 이루어진다. 때문에 메모리를 사용하게 된다.
또한, 입력값이 10000개로 제한되어있기 때문에 리스트를 미리 정해두는 것이 좋다.
arr = [] 에서 arr = [] * 10001
인덱스는 0 부터 시작하기 때문에 10001인 리스트를 생성했다

숫자가 들어오면, 해당하는 숫자의 index 에 +1 해준다.

이후 작은 수 부터 출력하면 되는데 2이상일 경우가 있기에 이중 for 문을 사용한다.