[백준 / BOJ] acmicpc 10989 수 정렬하기3

문제

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

10989번: 수 정렬하기 3

 

제한 메모리가 의도적으로 낮게 설정 되어있다.

처음엔 아무생각 없이 평소 하던대로 벡터에 입력 받고, sort함수로 정렬 후 출력했다. 

당연히 결과는 메모리 초과.

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string>
#include<cstring>
using namespace std;

int n;
vector<int> v;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	for (int i : v)
	{
		cout << i << "\n";
	}


}

 

 

찾아보니 정렬된 '결과' 만 출력하면 되므로 어떤 배열을 사용해서 입력 받아도 상관이 없다고 한다.

즉 sort 알고리즘을 사용하면서 쓰게되는 메모리들이 다 필요없다는것이다.

 

정답 코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string>
#include<cstring>
#include<sstream>
#include<deque>
using namespace std;

int n, k;
int arr[10001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		cin >> k;
		arr[k]++;
	}

	for (int i = 1; i <= 10000; i++)
	{
		while (arr[i] > 0)
		{
			cout << i << "\n";
			arr[i]--;
		}
			
	}


	cout << "\n";

}