[백준] 10989번 - 수 정렬하기 3 (C언어) - [Bronze1]

input	output
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

 

해당 문제는 시간 제한과 메모리 제한에 의해 많은 실패를 겪었던 문제이다. 

필자는 시간복잡도가 nlogn 정렬 알고리즘인 합병정렬과 힙정렬을 사용하였으나 시간초과가 발생하였다. nlogn의 시간복잡도를 가지는 알고리즘을 사용하지만 N의 범위가 (1 ≤ N ≤ 10,000,000) 이기 때문에 최악의 경우 퀵정렬은 O(n^2)의 형태를 띄어 시관초과가 발생하고 합병정렬은 최선, 최악, 평균의 모든 시간복잡도가 O(nlogn)이기 때문에 보다 더 빠른 알고리즘이 필요하다고 생각했다.

 

카운팅 정렬(Counting Sort)은 시간 복잡도가 O(n+k)로 비교 연산이 없는 정렬 방법이다. 우리는 집합 내의 가장 큰 정수를 알고 있고, 양의 정수를 오름차순으로 정렬하기 때문에 선형시간에 정렬할 수 있는 효율적인 알고리즘이다. 즉, 범위 조건이 있는 경우에 한해서 상당히 빠른 알고리즘이다. 

 

카운팅 정렬을 이용하여 해당 문제를 C 코드로 작성하면 다음과 같다.

#include <stdio.h>
#pragma warning(disable:4996)
#define max 10001

int main() {
	int n;

	scanf("%d", &n);

	int count[max] = { 0, }; // 배열 모든 원소 0으로 초기화

	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		count[x] = count[x] + 1;
	}

	for (int i = 1; i < max; i++) {
		for (int j = 1; j <= count[i]; j++) {
			printf("%d\n", i);
		}
	}

	return 0;
}

실행결과

 

[10989번]

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

10989번: 수 정렬하기 3

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview

 

[참고]

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221228361368 

11. 계수 정렬(Counting Sort)