백준 10989번 파이썬

1. 문제

2. 설명

카운팅 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때 사용 가능하다 .

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

값끼리의 비교가 아닌, 값의 빈도수를 저장하여 정렬하므로 속도도 매우 빠르다.

시간 복잡도는 O(N+K) 이다. -> k :  입력받은 수 중 max 값

---

카운팅 정렬 알고리즘

1. 숫자의 범위만큼 값이 0인 배열 을 만들어 놓는다.

여기서 주의할 점!

N의 범위는 10000이지만 배열의 인덱스는 0부터 시작하기 때문에 N이 10000일 경우를 대비하여  10001 개로 만들어줘야 한다.

2. x를 입력받고, x에 해당하는 인덱스에 1을 더해주며 각 x의 빈도수를 count 배열에 저장해준다.

3. for문을 돌며 저장된 i의 빈도수 만큼 i를 출력해준다. 

3. 코드

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)

---

평소 수를 정렬할 때 수끼리의 비교 또는 sort 내장 함수를 사용하였는데,

이번 문제를 통해 카운팅 정렬을 배웠다.

처음엔 익숙치 않아 이해하는 것이 까다로울 수 있지만, 수의 범위가 정해지면 정렬할 때 사용하기 매우 편리할 것 같다!