[python][백준/BOJ] 10989번 : 수 정렬하기 3 (메모리 초과 해결)

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

10989번: 수 정렬하기 3

 

▶ 메모리 초과 난 코드

• 빈 리스트를 만들어 입력값을 하나씩 append 해 준 후, 반복문을 돌며 정렬된 리스트 값을 출력함

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

nlist.sort()

for i in range(n):
    print(nlist[i])

✅ 최종 코드

import sys
n=int(sys.stdin.readline())
nlist=[0]*10000

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

for i in range(10000):
    if nlist[i]!=0:
        for j in range(nlist[i]):
            print(i+1)

 

✅ 문제 풀이

• 계수정렬을 사용함 (위의 코드처럼 짜면, 자동으로 정렬이 된다.)
• 입력 값은 10,000개의 작거나 같은 자연수가 주어지며, 중복이 가능하다는 것. 따라서, nlist를 빈 리스트로 만드는 것이 아니라, [0]*10000 으로 초기화해줌
• 계수정렬을 이용하면 메모리 초과는 해결되나 시간 초과 문제가 발생할 수 있음
• 시간 초과 해결은 input() 대신에 앞으로 sys.stdin.readline()을 사용하자!