[알고리즘/계수정렬/Python] 백준 10989 - 수 정렬하기 3
문제 : 10989번: 수 정렬하기 3 (acmicpc.net)
사용언어 : Python 3
시간제한 : 5초
메모리 제한 : 8 MB
문제 설명
수의 범위가 제한적이나 많은 수의 데이터를 정렬하는 문제이다. 제한 시간 내에 정렬을 수행 완료해야 한다.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
예제 입력
10
5
2
3
1
4
2
3
5
1
7
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
예제 출력
1
1
2
2
3
3
4
5
5
7
문제 특징
- 데이터의 개수가 최대 10,000,000
- 수의 범위가 1 ~ 10000으로 제한적임
- 입력 데이터가 많기 때문에 sys.stdin.readline()을 통해 입력을 받아야 시간 초과가 나지 않음
정렬해야 할 데이터의 개수가 최대 1천만 개까지 가능하다. 데이터의 개수가 크기 때문에 일반적인 경우 시간 복잡도가 O(nlog(n))인 퀵 정렬을 사용하여도 제한시간 (5초) 내에 해결을 하지 못한다. 이 보다 시간 복잡도가 적은 정렬 방식을 사용하여야 한다.
사용된 알고리즘 : 계수 정렬(Counting Sort)
정렬할 수의 범위가 제한적일 때 사용할 수 있다. 먼저 수의 범위 + 1 크기의 배열 a를 생성한다. 배열 a는 각 원소가 0으로 초기화된 배열이다. 정렬할 데이터를 순회하며 데이터 값이 i라고 할 때 a[i]에 1을 더해준다. 순회가 완료된 이후에 배열 a는 각 계수의 등장 횟수를 원소로 가진다. 아래 Ex 데이터를 정렬해야 한다고 하자.
Ex : 0, 3, 5, 7, 1, 7, 2, 2, 2, 3
위 Ex를 순회한 뒤 배열 a는 다음과 같다.
숫자 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
등장 횟수 | 1 | 1 | 3 | 2 | 0 | 1 | 0 | 2 |
배열 계수가 작은 순서대로 계수를 등장 횟수만큼 출력하여 오름차순을 구현할 수 있다.
- 0 1개 출력
- 1 1개 출력
- 2 3개 출력
- 3 2개 출력
- 4 0개 출력
- 5 1개 출력
- 6 0개 출력
- 7 2개 출력
Ex : 0, 1, 2, 2, 2, 3, 3, 5, 7, 7
시간 복잡도 : O(n)
파이썬 코드
import sys
test_case = int(sys.stdin.readline())
l = [0] * 10001
for _ in range(test_case):
d = int(sys.stdin.readline())
l[d] += 1
for i in range(10001):
if l[i] != 0:
for j in range(l[i]):
print(i)