Backjoon problem 10898 수 정렬하기 3- python

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

10989번: 수 정렬하기 3

 

• 입력과 출력

 

• 소스코드

import sys
num = [0] * 10001

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

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

• 해설

처음 이 문제를 보았을 그냥 단순히 sort(), sorted() 를 사용하면 풀 수있을 줄 알았지만 한번 제출 해보고 나서 확인해 보니

시간 제한 5초 , 메모리 제한 8 MB 라는 전제 조건이 있었다.

 

이 조건을 만족 할려면 기본 정렬 함수를 사용하면 Timsort()를 사용하고 리스트를 계속 생성해주면서 메모리 초과가 발생한다.

 

메모리 초과를 해결하기 위해서 계수 정렬을 사용 해서 풀면된다.

 

계수정렬은 우선 최대 배열 메모리를 초기화 시켜준다음 배열에 index를 입력 값과 같게 하면서 index를 증가시켜준뒤 0이 아닌 부분만 출력해주면 해결되는문제이다.