[알고리즘](파이썬)10989-수 정렬하기 3

문제

코드

import sys

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

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

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

 

코멘트

단순한 문제여서 금방 풀 수 있을 거라고 생각했는데 메모리 초과로 인해 코드 제출을 생각보다 많이 한 문제입니다.
공간 복잡도를 줄이는 것이 문제의 핵심입니다.

 

#메모리 초과 코드
import sys

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

s.sort()

for i in s:
    print(i)

✔️첫 코드의 문제점

-sort를 사용하면 메모리 초과가 나기 때문에 다른 방법 필요합니다.

-for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 메모리를 효율적으로 사용하지 못합니다.

 

✔️해결방법

[계수 정렬] 사용

-입력값이 10000개까지 주어지니 길이가 10001인 리스트를 만듭니다.

리스트 선언 시에 모두 0으로 초기화를 합니다.

-입력받을 때마다 그 수에 해당하는 인덱스에 +1을 해줘서 값으로 그 수의 개수를 담는다. -다시 배열을 돌면서 값이 0보다 큰 값을 가진 인덱스를 출력합니다.