백준 10989번 수 정렬하기3 [C/C++]

10989번: 수 정렬하기 3

문제

문제에 대한 설명을 읽어보면, 주어지는 수의 범위는 10,000보다 작거나 같다. 이렇게 숫자의 범위가 작은 문제는 카운팅 소트로 풀어야 하는 문제이다. 카운팅 소트는 입력되는 숫자의 범위가 작을 때 유용한 정렬이다. 숫자에 대한 비교가 이루어지지 않으므로, O(n)의 속도를 가진다. 구현된 것을 확인해보면 배열에 인덱스를 통해 바로 접근을 시도하기 때문에, 제한된 범위가 있는 문제에서는 상당히 효율적이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int check[10001];

int main()
{
	int test_case;
	int num;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		//cin >> num;
		scanf("%d", &num);
		check[num]++;
	}

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

	return 0;
}

그리고 scanf를 안쓰고 cin을 썼더니 시간초과가 났었다. 

 

iostream의 입출력을 사용하려면,

ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

위의 코드를 추가해서 사용하는 것을 추천한다.