문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이

시행착오

문제를 보고 '엥? 그냥 sort 문제 아닌가' 생각해서 벡터 생성 후 sort를 돌렸는데 메모리 초과가 떴다. 생각해보니 int형 배열을 10000000개나 만들면 40000000 byte고 이는 40메가??면 메모리 초과 뜰만 하다. 그래서 생각을 전환해서 입력받는 숫자가 10000까지이니 이에 대한 배열을 만들고 입력받을때마다 해당하는 배열의 카운트를 늘려 출력하는 식으로 했다.

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

int main()
{
	int n, num;
	vector<int> arr;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num);
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	for (auto x : arr)
		cout << x << '\n';
}

코드

#include <iostream>
using namespace std;

int main()
{
	int n, num;
	int arr[10001] = { 0, };
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num);
		arr[num]++;
	}
	for (int i = 0; i < 10001; i++)
	{
		for (int j = 1; j <= arr[i]; j++)
			cout << i << '\n';
	}
}