백준 2751

첫 번째 실패...

피벗 랜덤하겠다고 random 헤더 넣어서 해봤지만 오히려 더 무거워졌다.

#include <iostream>
#include <vector>
#include <random>

using namespace std;


void Qsort(vector<int>& a, int i, int j, mt19937& gen)
{		
	if (i >= j) return;
	uniform_int_distribution<int> dis(i, j);

	int pivot = dis(gen);
	int left = i;
	int right = j;

	while (left <= right)
	{
		while (a[left] < pivot)
		{
			left++;
		}
		while (a[right] > pivot)
		{
			right--;
		}
		if (left <= right)
		{
			swap(a[left], a[right]);
			left++;
			right--;
		}
	}
	Qsort(a ,i, right, gen);
	Qsort(a , left, j, gen);
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	

	vector<int> vectors;

	int input = 0;
	cin >> input;

	for (int i = 0; i < input; ++i)
	{
		int num = 0;
		cin >> num;
		vectors.push_back(num);
	}

	random_device rd;
	mt19937 gen(rd());

	Qsort(vectors, 0, vectors.size() - 1, gen);

	for (int i = 0; i < vectors.size(); ++i)
	{
		cout << vectors[i] << "\n";
	}
	return 0;
}

 

두 번째 실패...

 

런타임 오류가 나옴. 아마 배열 관련해서 크기 문제가 생긴듯하다.

#include <iostream>
#include <vector>
#include <random>

using namespace std;


int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vectors;

	int input = 0;
	cin >> input;

	for (int i = 0; i < input; ++i)
	{
		int num = 0;
		cin >> num;
		int a = num + 1;
		if (num < vectors.size())
		{
			vectors[num]++;
		}
		else
		{
			vectors.resize(a);
			vectors[num]++;
		}
	}

	for (int i = 0; i < vectors.size(); ++i)
	{
		if (vectors[i] == 1)
		{
			cout << i << "\n";
		}
	}

	return 0;
}

결국 세 번째 정답.

 

은 그냥 sort 썻다....

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

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);



	vector<int> vectors;

	int input = 0;
	cin >> input;

	for (int i = 0; i < input; ++i)
	{
		int num = 0;
		cin >> num;
		vectors.push_back(num);
	}

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

	for (int i = 0; i < vectors.size(); ++i)
	{
		cout << vectors[i] << "\n";
	}
	return 0;
}