[C/C++] 백준 10989번 - 수 정렬하기 3(Counting Sort)

 

 

 

<코드>

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int ans[10001];
int main(void)
{
	int N;
	int x;
	scanf("%d", &N);

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


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

 

문제를 보고 입력의 개수가 최악의 경우 1천만 개가 주어지는 것을 보고 단순히 배열로 저장해서 정렬하면 에러가 날 것을 예상하였다. 입력에서 입력되는 수의 범위가 1~10000 사이 이므로 카운팅 정렬(Counting Sort) 해야겠다는 생각이 들었고 입력되는 값을 받아 그 수에 해당하는 배열의 인덱스를 증가하는 방식으로 구현을 하였다.

 

연산을 최대한 빠르게 처리하기위해 cin , cout, endl 말고 scanf, printf를 사용하도록 한다.

 

 

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

10989번: 수 정렬하기 3