[알고리즘/계수정렬/Python] 백준 10989 - 수 정렬하기 3

문제 : 10989번: 수 정렬하기 3 (acmicpc.net)

10989번: 수 정렬하기 3

 

사용언어 : 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

 배열 계수가 작은 순서대로 계수를 등장 횟수만큼 출력하여 오름차순을 구현할 수 있다. 

 

1. 0 1개 출력
2. 1 1개 출력
3. 2 3개 출력
4. 3 2개 출력
5. 4 0개 출력
6. 5 1개 출력
7. 6 0개 출력
8. 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)