BOJ 10989 - 수 정렬하기 3

• 10000 이하의 자연수가 N(N<=10^7)개 주어질 때 3sec, 8MB 안에 정렬한 결과를 출력하는 문제이다.

문제 풀이

• 시간만 보고 STL sort를 썼다가 메모리초과를 받아서 당황했다.

• 들어오는 수의 범위를 이용해서 counting sort해야한다.

소스코드

#include<cstdio>
#include<vector>
using namespace std;

int main()
{
	int n;
	vector<int> a(10000, 0);
	scanf("%d", &n);
	for(int i=0;i<n;i++){
		int t;
		scanf("%d", &t);
		a[--t]++;
	}
	for(int i=0;i<10000;i++) for(int j=0;j<a[i];j++) printf("%d\n", i+1);
}

• 내 코드는 2456ms가 걸렸는데 가장 빠른 코드는 실행시간이 무려 76ms였다. 입력을 scanf로 받지 않고 통째로 받아서 버퍼에서 바로 계산하는 방식인 것 같은데 제대로 이해하진 못했다.