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

문제 링크

10989번: 수 정렬하기 3

 

풀이

정렬 문제. 입력을 다 받아서 sort하려고 하면 메모리 초과가 난다..
입력 길이는 최대 10,000,000라서 int형으로 만들어줘도 4B * 10000000니까 40MB로 메모리 초과가 난다.
대신 각 값은 10,000으로 엄청 작은 편이라 계수 정렬을 사용하면 된다. 계수 정렬의 시간 복잡도는 O(n)

1. 배열을 초기화해준다. 입력의 최대값은 10000이므로 10001 사이즈로 만들어줘야 한다. 처음에 이것때문에 틀림
2. 입력을 받으면서 배열을 갱신해준다. 각 인덱스의 값은 인덱스의 숫자가 몇 개 들어있는지가 들어가게 된다.
3. 배열이 완성됐으면 인덱스의 값만큼 인덱스를 출력해준다.

5

1

3

1

4

2

3

5

1

7

이게 입력 값이라면, 완성된 배열은

0	1	2	3	4	5	6	7	8	... 10000
0	3	1	2	1	2	0	1	0	...

이렇게 될 것이다. 말 그대로 인덱스만큼 수를 세서 넣어주므로 카운팅 정렬(계수 정렬)임

 

코드

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	int arr[10001] = { 0, };
	for (int i = 0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		arr[tmp]++;
	}

	for (int i = 0; i < 10001; i++)
	{
		for (int j = 0; j < arr[i]; j++)
		{
			cout << i << '\n';
		}
	}

	return 0;
}