백준 10989번 수 정렬하기 3 파이썬

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

10989번: 수 정렬하기 3

 

답안

import sys

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

for _ in range(n):
    count[int(sys.stdin.readline())] += 1
    
for i in range(1, 10001): # 자연수는 1부터
    for j in range(count[i]):
        print(i)

 

 

---

 

이 문제를 처음 접근 했을때, 정말 여러 정렬을 많이 사용 했었다.

파이썬에 있는 기본 정렬 sort()부터 해서 퀵정렬, 합병정렬, 계수정렬(리스트에 넣는) 등등 을 사용 했었다.

뻔한 결과지만

전부다 메모리 초과가 떴었다..

한참을 생각해 보다 최대 천만 개의 숫자를 다 넣고 출력 한다는 게 오래 걸릴뿐더러

애초에 리스트 안에 그렇게 많은 데이터가 들어가면 메모리가 상당히 많이 사용이 될 것이다.

그래서 좀 다른 방법으로 생각을 해봤다.

count 리스트를 초기화해주고 (고정 크기 0부터 10000까지)

각각 나오는 숫자 자리를 +1씩 올려준다.

 

• 그림으로 쉽게 설명을 하자면

   이렇게 초기화 해주고, n = 4

   input()을 3, 1, 5, 3 로 받았다고 생각해보자.

   그럼 count 리스트는

   이렇게 될 것이다.

   마지막에는 최대 경우를 생각하여 1부터 10000번째까지의 count된 것들을 출력해 주면 된다.

   물론 0번 나온 것은 출력이 안되게 짰다.

   이러면 고정 크기의 메모리만 사용하기 때문에 과한 메모리 손실을 막을 수 있다. ( 메모리 초과 방지 )

   또한 굳이 정렬을 안 해도 된다. ( 시간 초과 방지 )