백준 10989 수 정렬하기 3(c++)

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<int>count(10001);
	
	for(int i=0;i<n;i++)
	{
		int num;
		cin>>num;
		count[num-1]++;
	}
	for(int i=0;i<=10000;i++)
	{
	
		for(int j=0;j<count[i];j++)
		{
			cout<<i+1<<'\n';
		}
	}
}

<풀이과정>

이 문제는 다른 정렬 문제랑은 다르게 시간복잡도를 고려하는 것이 아닌, 메모리를 고려해야 한다.

될수 있는 n의 최댓값이 10000000인데, 배열의 메모리를 10000000만큼 할당한다면 메모리 초과가 뜰 수 밖에 없다.

그래서 카운팅 정렬이란 것을 적용시켜야 된다.

될 수 있는 수는 10000까지이므로 같은 값이 나온다면 그 개수를 늘려주는 것이 카운팅 정렬이다.