[Python] 수 정렬하기 3 - 정렬

10989 문제

해당 문제 링크

풀이

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)

해석

메모리 초과, 시간 초과 문제가 생겼다.. 어떻게 해야 하는지 방법을 검색하고 코드도 참고하여 해결했다.

수 정렬하기 2 문제를 가져와 돌렸을 때는 메모리 초과가 됐다.
for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 메모리를 효율적으로 사용하지 못한다.(= for 문의 스텝이 진행될 때마다 메모리 재할당이 일어난다. l 변수에 append하기 때문이다. 속도저하가 일어나고 메모리를 효율적으로 사용하지 못한다. 결과는 제대로 나와도 이런 코드는 효율적이지 못하다.)

import sys

n=int(input())
l=[]
for _ in range(n):
    l.append(int(sys.stdin.readline()))
for i in sorted(l):
    print(i)

일반적으로 입력값이 크지않은 경우에는 상관없지만 이렇게 입력값이 극한으로 많이 주어질때는 메모리를 좀 더 효율적으로 관리해야 한다.

참고한 코드를 보면,
입력값이 10000개까지 주어질 수 있으니 10000개 만큼의 리스트를 만든다.
그러나 인덱스 0부터 세기 때문에 이를 계산하기 편하게 길이가 10001인 리스트를 만든다.

num_list = [0] * 10001

리스트에 각 요소마다 0을 할당해놓고 입력 값을 받을 때마다 그 입력값과 같은 인덱스에 +1씩 해준다.

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

나중에 입력을 다 받고나면 0보다 큰 요소를 갖는 인덱스들을 찾아서 그 수만큼 인덱스를 출력해주면 된다.

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