counting sort 문제 풀어보기

#include <iostream>
using namespace std;


int main() {
	int n;
	cin >> n;
	int arr[10];//n 1~10
	for (int i = 0;i < n;i++) {
		cin >> arr[i];
	}
	int dat[100] = { 0 };
	
	for (int i = 0; i < n;i++) {
		dat[arr[i]] += 1;
	}
	int sum = 0;
	int summingup[100] = { 0 };
	for (int i = 0; i < 21;i++) {
		sum += dat[i];
		summingup[i] = sum;
	}
	for (int i = 0; i < 10;i++) {
		cout << summingup[i];
	}
	cout << endl;
	int ans[11];

	for (int i = 0; i < n;i++) {
		int temp = summingup[arr[i]];
		ans[temp - 1] = arr[i];
		summingup[arr[i]]--;
	}
	for (int i = 0; i < n;i++) {
		cout << ans[i];
	}
}

O(n + k) 속도를 보이는 Counting Sort를 구현하고자 합니다.
n개의 숫자를 입력받고, 그 과정을 출력 해 주세요.

Counting Sort 과정 1 : DAT 처리
Counting Sort 과정 2 : 누적합 구하기 ( [0] ~ [9] index 까지 총 10개 누적값만 출력 해 주세요. )
Counting Sort 과정 3 : 정렬하기 ( 정렬 결과를 출력 해 주세요. )

정렬하는 과정에서 만들어지는 누적값과 정렬값을 출력 해 주세요.


[세부 조건]
1. 정렬할 숫자의 최소 값 : 1
2. 정렬할 숫자의 최대 값 : 20
3. 1 <= n <= 10

 

 

입력 예제

5 5 2 2 1 2

출력 결과

0144455555 12225

 

 

좀 복잡하지만 정리하면.. 

 

1 DAT 

입력후 dat[100]에다가 집어넣는다.

 

2 summingup

누적합 배열에다가 dat 개수만큼 누적합 정리한다. 

 

그리고 프린트 (이건 문제의 요구사항)

3 마지막으로 summingup한 누적합 결과에 따라

새로운 배열 ans에다가 정리한다.

누적합-1 로 하면 자동으로 인덱스가 부여됨