[Baekjoon][Python][10989] 수 정렬하기3

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

10989번: 수 정렬하기 3

 

설명

이전문제에서보다 N의 범위가 증가하였습니다. N의 범위 때문에 정렬 알고리즘(병합, 퀵, 힙)을 사용하기엔 어렵고 수의 범위가 작아진 것을 확인할 수 있습니다( 0<= N <=10000) 시간 복잡도 O(N) 이 걸리는 카운팅 정렬을 사용하였습니다.

 

소스코드

import sys

N = int(sys.stdin.readline())
list = [0] * 10001

for _ in range(N) :
    val = int(sys.stdin.readline())
    list[val] += 1

for idx,value in enumerate(list) :
    if value > 0 :
        for _ in range(value) :
            sys.stdout.write(str(idx)+'\n')

소스설명

• 0 ~ 10000 의 숫자를 담아내기 위해 리스트의 크기를 10001로 잡고 카운팅을 위해 0으로 초기화 하였습니다.
• 해당 숫자가 등장할때마다 카운팅을 1씩 증가시켜 리스트를 돌면서 카운팅이 1 이상인 숫자를 카운팅 만큼 출력하였습니다.