백준 10989: 수 정렬하기 3

문제

https://www.acmicpc.net/problem/10989

1. 수의 개수인 N을 입력받는다.

2. N개의 숫자를 입력받는다.

3. 입력받은 수를 오름차순으로 정렬하여 출력한다.

 

 

풀이 및 알고리즘

처음에는 수를 입력할 때마다 리스트에 append하고, 파이썬에 내장되어 있는 sort 함수를 사용하였다.

하지만 메모리 초과가 발생했다. 찾아보니 입력받자마자 원소를 append하는 것은 시간이 오래 걸린다는 것을 알게 되었다.

리스트의 append는 비용이 발생한다.
-> python의 리스트는 동적 배열인데, append할 때 메모리가 꽉 차면 더 큰 새로운 배열을 만들고 기존 데이터를 복사한다.
-> 그래서, 메모리가 작게 설정되어 있는 이 문제를 풀기 위해서는 이러한 복사하여 중복되는 메모리 문제를 해결해야 한다.

 

그럼 메모리초과를 해결하기 위해서는 어떻게 해야할까?

기존 구현 방식에서의 문제가 append할 때 비용이 발생한다는 문제였는데, 이를 해결하기 위해서는 공간을 미리 할당하는 것도 방법이다.

공간을 미리 할당해두면 복사가 필요없어서 훨씬 빠르다고 한다.

 

 

정답

import sys
N = int(sys.stdin.readline())
answer = [0] * 10001

for i in range(N) :
    a = int(sys.stdin.readline())
    answer[a] += 1

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

 

문제에서 최대 입력이 10000라고 했으므로, 10001만큼의 공간을 미리 할당해둔다.

그래서, 특정 숫자가 나왔을 때 그 숫자를 인덱스로 갖는 공간에 접근하여 1씩 증가시킨다.

이렇게 하면 불필요한 중복을 없앨 수 있을 뿐 아니라 메모리초과 문제도 해결할 수 있다.