[백준] 알고리즘 10909번 - 수 정렬하기3 문제

#include <bits/stdc++.h>
using namespace std;
int arr[10001];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		arr[tmp]++;
	}
	for (int i = 1; i < 10001; i++) {
		for (int j = 0; j < arr[i]; j++) cout << i << "\n";
	}
}
 

기존의 sort를 이용하여 문제를 해결하게 되면, 런타임 에러가 뜰것이다.

이런 문제는 어떻게 접근해야 하는가.

계수 정렬(counting sort)을 이용해야한다.

1. 각 숫자가 몇번 등장하는지 세어준다.

2. 등장 횟수를 누적합으로 바꿔준다.

계수 정렬의 완벽한 설명을 해주는 사이트가 있습니다. 참고하시면 많은 도움되실거에요

계수정렬

Counting Sort