백준 BOJ 10989 - 수 정렬하기 3

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

10989번: 수 정렬하기 3

#include <stdio.h>

int sort[10001] = {0};

int main(){
	int n,k;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &k);
		sort[k]++;
	}
	for(int i=0; i<=10000; i++){
		if(sort[i] != 0){
			for(int j=0; j<sort[i]; j++){
				printf("%d\n",i);
			}
		}
	}
	return 0;
}

어디선가 봤었던 특이한 정렬방법을 이용해보았다.

수의 범위가 10000 이하의 자연수이기때문에 가능했던 방법인데

수의 범위만큼의 배열을 만들고,

입력된 수를 인덱스값으로 해서

해당 인덱스값에 그 수가 몇번 입력됬는지를 저장한다.

그 이후 작은값부터 큰 값으로 올라가면서(큰 값부터시작하면 역순으로 정렬됨)

입력된 횟수만큼 다시 출력해서 정렬한다.

​

입력범위가 커지면 공간복잡도도 커진다는 단점이 있지만,

처리속도가 굉장히 빨라서 인상깊었던 방법이었다.