[백준] 10989 수 정렬하기 3 (파이썬 python)

 

 

문제 링크

 

 

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

10989번: 수 정렬하기 3

 

 

문제

 

 

 

 

 

문제 풀이

 

 

문제만 봐서는 너무 간단해서 단순하게 접근했다가 메모리 초과가 나왔다.

처음 제출했던 코드는

 

import sys
input = sys.stdin.readline

n = int(input())
array = []
for i in range(n):
    array.append(int(input()))

array.sort()

for i in range(len(array)):
    print(array[i], end='\n')

 

 

어떻게 바꿔야할지 감이 잡히지 않아 찾아보니

append를 사용하게 되면 메모리 재할당이 이루어져 메모리를 효율적으로 활용할 수 없다고 한다.

또 리스트의 크기를 10000으로 제한해두는 것이 필요했다.

크기가 10000인 리스트의 각 값을 0으로 할당시켜놓고,

인덱스에 해당하는 값이 들어올 경우 +1을 해주고 나중에 1이 값으로 할당된 인덱스만 불러오면 되는 것이다.

 

 

바뀐 정답 코드는 다음과 같다.

 

import sys

n = int(sys.stdin.readline())
array = [0] * 10001
for i in range(n):
    array[int(sys.stdin.readline())] += 1

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