[10989] 수 정렬하기 3

브론즈 1

계수 정렬을 이용하는 문제이다

 

계수 정렬(Counting Sort) : 크기를 개수로 세는 정렬. 범위만큼의 배열을 설정한다. 시간 복잡도는 O(n). 메모리가 많이 요구되고 데이터가 많아질수록 시간이 매우 오래 걸리는 단점이 있다.

 

여기서는 입력받는 자연수의 범위가 10000까지기 때문에 배열의 크기를 10001로 설정해주었다

원소를 입력받으면 A[원소]++; 를 해준다

그리고 출력할 때 배열 순서대로 출력하면 정렬된 것처럼 보인다

 

처음에는 cout을 사용하였으나 시간초과 때문에 실패하여 시간을 줄여주는 코드 2줄을 작성하였고 cout을 printf로 변경해주었다

#include <iostream>
using namespace std;

int A[10001];
int N;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int x;
		cin >> x;
		A[x]++;
	}

	for (int i = 1; i <= 10000; i++) {
		if (A[i]) {
			for (int j = 0; j < A[i]; j++) {
				printf("%d\n", i);
			}
		}
	}
}