[파이썬] 백준 - 10989: 수 정렬하기 3

---

백준 문제 특성상 난이도를 포함해서 정답 비율이 20%대로 현저히 낮다면

시간제한 혹은 메모리 제한에 걸릴 확률이 높다. 이 문제도 그런 부류다.

 

---

문제

10989번: 수 정렬하기 3

---

풀이

원래라면 리스트 안에 받은 배열을 넣고, 정렬하고 하나씩 빼는 간단한 방법을 썼을 것이다.

그런데 이렇게 하면 메모리가 초과된다.

 

그래서 10,000보다 작거나 같은 자연수라는 힌트를 갖고, 10001개의 0으로 이루어진 배열을 만든다.

10001개인 이유는 리스트의 인덱스로 결과물을 출력해야 하기 때문. 이후에 조작해주는 것 보다 차라리 10001개로 만드는 것이 편리하다.

 

1은 2개 이런식.

import sys

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

for i in range(n):
    lists[int(sys.stdin.readline())] += 1	
    # 0으로 된 리스트의 인덱스를 입력 받고 해당 숫자가 존재하면 1을 더하는 방식. 
    #2이면 두 번 출력하도록 아래에서 진행
    
for i in range(10001):
    if lists[i] != 0:	# 우선 0이면 해당 숫자가 없는 것 이므로
        for j in range(lists[i]):	# 있으면 해당 숫자만큼
            print(i)	# 출력