백준 10989번 : 수 정렬하기 3

이 문제는 메모리 제한이 8MB이며, 입력받는 수의 개수는 N(1 ≤ N ≤ 10,000,000)이다. vector에 입력받은 수를 저장한다면 최대로 필요한 메모리 공간은 size(int) * 10,000,000 = 4byte * 10,000,000 = 40,000,000 byte = 38.14.....MB 이다. 입력된 수의 개수에 상관없이 메모리 공간을 효율적으로 사용해 정렬된 수를 저장할 필요가 있다. 수의 범위는 10000 이하 이므로 숫자-입력횟수 쌍으로 값을 저장하면 필요한 메모리는 4byte*10,000*2 = 80000byte = 0.716...MB이므로 메모리를 줄일 수 있다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
	int N;
	scanf("%d", &N);

	vector<int> numbers;
	for (int i = 0; i < N; i++)
	{
		int number = 0;
		scanf("%d", &number);
		numbers.push_back(number);
	}

	sort(numbers.begin(), numbers.end());
	numbers.erase(unique(numbers.begin(), numbers.end()));
	for (int number : numbers)
	{
		printf("%d\n", number);
	}
	return 0;
}