[BOJ]10989번: 수 정렬하기 3 (c++)

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

10989번: 수 정렬하기 3

 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<int> v(10000 + 1);
	for (int i = 0; i < N; ++i)
	{
		int num;
		cin >> num;
		++v[num];
	}

	// [1, 10000] 범위의 수를 입력된 횟수만큼 출력
	for (int i = 1; i <= 10000; ++i)
	{
		if (v[i] > 0)
		{
			for (int j = 0; j < v[i]; ++j)
			{
				cout << i << '\n';
			}
		}
	}

	return 0;
}

 

 

8MB로 주어진 메모리제한을 처리하는 문제이다.

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.

수가 1천만개가 주어지므로 이를 모두 벡터에 저장하면

4byte * 1천만 = 4천만 byte의 메모리 공간을 필요로 한다.

하지만 메모리 제한은 8MB = 1024byte * 8 = 8192byte 이기 때문에 어림도 없다!

 

 

 둘째 줄부터 N개의 줄에는 숫자가 주어진다.
이 수는 10,000보다 작거나 같은 자연수이다.

대신에 입력되는 수의 크기 제한을 봤을때,

동일한 숫자가 여러번 입력될 것임을 예측할 수 있다.

 

따라서 숫자 i가 입력되는 횟수를 저장할 벡터를 만들어서

입력된 횟수만큼 숫자 i를 출력해 주면 된다.