백준 10989 counting sort c++

문제 밑에 힌트가 적혀있다

카운팅 정렬을 이용하면 더욱 빠르게 정렬할 수 있다고

counting sort~ 밤 하늘에 퍼어얼

 

 

즉 시 알고리즘 자료 찾아

정리를 하자면

배열로 먼저 받고

일일히 비교하며 정렬하는 것이아니라

해당 key값이 몇 번 나왔는지 count하고

key값이 낮은 값부터 count만큼 출력하면

비교 정렬을 하지 않아도 오름차순으로 정렬이 가능하다

 

 

그래서 이 강의 자료를 보고 만든 코드

#include <iostream>

using namespace std;



int main() {
	int n;		//원소의 개수
	int k = 0;	//원소는 1~k사이의 수
	cin >> n;

	int* A = new int[n+1];	//처음 값 입력받을 배열
	int* B = new int[n+1];	//정렬된 원소 받을 배열

	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		
		if (A[i] > k)
			k = A[i];
	}
	int* C = new int[k+1];	// 원소 개수 셀 배열
	for (int i = 1; i <= k; i++) {
		C[i] = 0;
	}

	for (int i = 1; i <= n; i++) {
		C[A[i]] += 1;
	}

	for (int i = 2; i <= k; i++) {
		C[i] = C[i] + C[i - 1];
	}

	for (int i = n; i >= 1; i--) {
		B[C[A[i]]] = A[i];
		C[A[i]]--;
	}

	for (int i = 1; i <= n; i++) {
		cout << B[i] << "\n";
	}
	

	delete A;
	delete B;
	delete C;

	return 0;
}

 

이것의 결과는

메모리 초과

질문 검색에서 조금 찾아보니

배열에 일일히 다 받지 않아도 된다고 한다

 

아 옳다구나

이 강의자료에서는

배열이 3개가 나오는데

10989번에서는

1~10000사이의 수만 나오니까

하나의 counting하는 배열만 만들면되겠구나

 

 

 

#include <iostream>

using namespace std;

#define MAX 10001

int main() {
	int n,input;
	int A[MAX];
	for (int i = 1; i < MAX; i++) {
		A[i] = 0;
	}
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> input;
		A[input]++;
	}

	for (int i = 1; i <= n; i++) {
		if (A[i] != 0) {
			for (int j = A[i]; j > 0; j--) {
				cout << i << "\n";
			}
		}
	}
	return 0;
}

이 코드의 결과는

출력초과 

뭐가 문제지 고민하다가

사용자한테 값을 입력받을때

max값을 구하고

반복문을 max까지만 돌면

출력초과가 안나겠구나!

라고생각했다

 

 

 

 

 

고친 코드

#include <iostream>

using namespace std;

#define MAX 10001

int main() {
	int n,input,max=0;
	int A[MAX];
	for (int i = 1; i < MAX; i++) {
		A[i] = 0;
	}
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> input;
		A[input]++;
		if (input > max)
			max = input;
	}

	for (int i = 1; i <= max; i++) {
		if (A[i] != 0) {
			for (int j = A[i]; j > 0; j--) {
				cout << i << "\n";
			}
		}
	}
	return 0;
}

결과는?

시간 초과

아까는 출력초과였는데

이번엔 시간 초과가 떴다

 

흠 질문 검색에서 조금 힌트를 얻어

ios_base::sync_with_stdio(false);

이 코드를 추가해주면 속도가 빨라진다는 말을 들어

한 줄 추가해주었다

 

 

#include <iostream>

using namespace std;

#define MAX 10001

int main() {
	ios_base::sync_with_stdio(false);
	int n,input,max=0;
	int A[MAX];
	for (int i = 1; i < MAX; i++) {
		A[i] = 0;
	}
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> input;
		A[input]++;
		if (input > max)
			max = input;
	}

	for (int i = 1; i <= max; i++) {
		if (A[i] != 0) {
			for (int j = A[i]; j > 0; j--) {
				cout << i << "\n";
			}
		}
	}
	return 0;
}

그랬더니

성공했다

 

보통 정렬하면 비교정렬을 생각하는데

비교 하지않고도 정렬을 할 수 있는

counting sort의 방식은 매우 신기했다

그리고 O(n)이라 매우 빠르다

알고리즘 수업들을때는 주의깊게 안봤는데

이렇게 다시보니 신기하다