[BOJ] 10989 번 - 수 정렬하기 3 파이썬

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

10989번: 수 정렬하기 3

 

카운팅 정렬을 사용해서 풀어야 하는 문제이당

 

카운팅 정렬은 "특정한 조건" 이 성립해야지 사용할 수 있는 정렬이다

 

#특별한 조건이란 ? 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때   사용이 가능하다 

 

이 문제의 경우에는 문제에 숫자의 범위가 10000까지 라고 정의되어있이 때문에 카운팅 정렬을 사용할 수 있다

 

시간 복잡도는 O(N+K) 로 아주아주 빠른 편

 

 

#count sort 를 이용해서 풀어보아용
#숫자의 범위가 10000 까지라는 조건이 있기 때문에 count 를 10001 까지 해주자
import sys

n = int(input())

count = [0]*10001

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

for i in range(len(count)):
    for j in range(count[i]):
        print(i)

 

숫자의 범위만큼 [0] 을 만들어 놓는다 여기서 주의할 점은 10000 이지만 0을 포함하기 때문에 10001 개로 만들어줘야 한다는 것

숫자를 입력받았을때 count[x] 를 +1 을 해주고

 

for 문을 통해서 출력을 해주면 해결 가능하다