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

알고리즘

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

min._.uuk_ 2023. 5. 23. 21:35

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;
}

실행결과