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

10989번: 수 정렬하기3

이번 문제를 algoritm을 include하여 qsort 내장 함수를 이용하고자 하면 시간초과, 메모리초과가 발생한다.

입력되는 값의 개수가 무려 10,000,000개가 될 수 있기 때문이다.

어떻게 해야할지 감도 안 잡히다가, 질문 검색 탭에서 힌트를 얻었다.

카운팅 정렬을 이용하면 메모리 초과를 해결할 수 있다고 한다.

문제를 다시보니, 값의 최대값이 10,000으로 제한돼 있다.

카운팅 정렬에서는 각 값이 몇 번씩 등장했는지 세어준 다음에 값 * 카운트를 새로운 배열에 저장하여 인덱스로 활용한다.

하지만 여기서는 새로운 배열에 저장하려고 하다가는 메모리 초과가 뜨기 떄문에, 카운트만을 활용했다.

처음에 크기가 10,000인 int 배열을 선언한 후 각 값이 입력되면 바로바로 카운트했다.

이후, 카운트 배열을 이용하여 카운트된 횟수만큼 해당하는 값을 출력하며 마무리했다.

#define MAX 10000

#include <cstdio>

using namespace std;

int main()
{
	int N, K;
	scanf("%d", &N);
	int* count = new int[MAX];
	for (int i = 0; i < MAX; i++) {
		count[i] = 0;
	}
	for (int i = 0; i < N; i++) {
		scanf("%d", &K);
		count[K - 1]++;
	}
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < count[i]; j++) {
			printf("%d\n", i + 1);
		}
	}
	delete[] count;
	return 0;
}

알고리즘 이론 공부의 필요성을 느꼈다.