[c++] 백준 10989번 - 수 정렬하기 3

# 백준 10989번 URL

10989번: 수 정렬하기 3

숫자를 N개 만큼 입력 받는다. (각 숫자는 10000보다 작거나 같은 자연수)

이 문제는 속도가 O(nlog)이 나오는 퀵 정렬, 병합정렬, 힙정렬을 사용하게 되면 메모리 초과가 나오게 된다.

 

입력값이 10000보다 작다는 조건이 있으므로 여기서는 계수정렬을 사용한다.

(계수정렬은 O(n)의 시간복잡도를 가진다)

 

또한 c++의 입력, 출력 방식인 cout, cin을 사용하게 되면 시간초과가 일어나므로 여기서는 printf()와 scanf()를 사용하였다.

 

#include <iostream>

using namespace std;

int n;
int arr[10001];

int main() {
	int num=0;
	scanf_s("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf_s("%d", &num);
		arr[num]++;
	}
	
	for (int i = 0; i < 10001; i++) {
		while (arr[i] != 0) {
			printf("%d\n", i);
			arr[i]--;
		}
	}
}