[BOJ] 10989. 수 정렬하기3(python)

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

10989번: 수 정렬하기 3

문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

문제 해결

import sys
input = sys.stdin.readline

N = int(input())
arr =[0] * 10001

for i in range(N):
    arr[(int(input()))] += 1
for i in range(len(arr)):
    for j in range(arr[i]):
        print(i)

 

문제 풀이 설명

이 문제는 카운팅 정렬(계수 정렬)을 위한 문제이다.

입력되는 데이터의 크기(size 말고 입력되는 숫자)가 크지 않을때 효과적인 정렬 알고리즘이다.

우리가 쓰는 python 의 내장함수 sort()는 퀵정렬을 사용해 O(nlogn)의 시간복잡도를 가지지만, 계수 정렬은 O(n + k)의 시간복잡도를 가진다. 여기서 k는 입력된 데이터 중 가장 큰 값을 의미하며, n 보다 작을 경우 n으로 수렴하겠지만 n 보다 클 경우 무한대로 커질 수 있는 단점이 있다.

 

문제에서는 카운팅 정렬을 사용하라고 입력되는 데이터의 크기는 10000보다 작다고 명시했으며,

이를통해 카운팅 정렬을 사용해 문제를 해결했다.

 

1) 입력된 데이터를 인덱스로 하는 리스트(arr)를 생성한다.(크기는 입력된 데이터 중 max값 + 1)

2) 그 후 arr의 길이만큼 돌면서 각 arr[i]의 수만큼 i를 출력하면 끝

 

카운팅 정렬(Counting Sort)

 

카운팅 정렬(계수 정렬)

Counting Sort

위의 링크는 계수 정렬을 잘 설명해주는 사이트이다.

먼저 정렬할 리스트를 입력 또는 생성한다.

arr = [1,4,5,3,4,0,0,5,0,2,1,5,3,0,4,3]

그 후 해당 값을 인덱스로 하는 리스트를 생성해 +1 씩 추가한다.

count = [0] * (max(arr)+1) #최댓값의 +1 한 만큼 생성
for i in arr:
	count[i] += 1
# count = [4,2,1,3,3,3]

그 이후 for문을 돌며 각 인덱스의 수만큼 인덱스를 출력하면 된다.

for i in range(len(count)):
	for j in range(count[i]):
    	print(i)
# 출력결과 = 0,0,0,0,1,1,2,3,3,3,4,4,4,5,5,5

입력되는 데이터의 크기가 작을 때 유용하게 사용할 수 있는 카운팅 정렬에 대해 알아봤다.