[백준 10989번] 수 정렬하기 3 in python

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

 

 

---

이번 문제는 시간 초과가 아니라 메모리에 대한 문제였다.

보통 정렬을 할때는 시간 복잡도를 줄이는데 이번엔 메모리 할당에 대한 문제가 나와 신선했다.

 

병합정렬을 쓰거나, 기존에 파이썬에 내장되어 있는 정렬함수를 써도 메모리 초과 문제를 해결할 수 없었다.

여러 블로그를 보니깐 값을 넣어줄 때 append가 문제라고 한다.

 

코드를 보니 새로운 방법으로 문제를 푼 것이 보였다.

기존에 값이 들어갈 범위까지 리스트를 생성한다. 그 후 append를 쓰지 않고 num_lst[찾을 인덱스]로 사용하면서 해당되면 +1을 해주는 방식으로 진행했다.

이렇게 하면 리스트를 계속해서 찾아야하니 시간 복잡도는 크게 증가하나 기존의 설정된 리스트에서 찾아주기만 하니 메모리 초과 문제는 해결되었다.

import sys

n=int(input() )
num_lst=[0]*10001

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

for i in range(10001):
  if num_lst!=0:
    for _ in range(num_lst[i]):
      print(i)

신박해서 언젠가 다시 기억하라고 저장해놓는다.