40번 투포인트 알고리즘(Microsoft interview 문제)

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

int main(void)
{
	
	int N = 0;
	int M = 0;
	int cnt = 0;
	cin >> N;
	int arr[60000];
	vector<int> result(N);
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	cin >> M;
	for (int i = N; i < N + M; i++)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = N; j < N + M; j++)
		{
			if (arr[i] == arr[j])
			{
				result[cnt] = arr[i];
				cnt++;
				break;
			}
			
		}
	}
	int min = 0;
	int mtemp = 0;
	int temp = 0;
	for (int i = 0; i < N; i++)
	{
		min = result[i];
		mtemp = i;
		for (int j = i; j < N; j++)
		{
			if (min > result[j])
			{
				min = result[j];
				mtemp = j;
			}
		}
		temp = result[i];
		result[i] = result[mtemp];
		result[mtemp] = temp;
	}

	for (int i = 0; i < N; i++)
	{
		if (result[i] != 0)
		{
			cout << result[i] << " ";
		}
		
	}
}

위 방법은 투포인트 알고리즘X 따라서 타임리밋 발생..

 

투포인트 알고리즘

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

int main(void)
{
	int N = 0;
	int M = 0;
	cin >> N;
	vector<int> arr(N);
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());
	
	cin >> M;
	vector<int> brr(M);
	for (int i = 0; i < M; i++)
	{
		cin >> brr[i];
	}
	sort(brr.begin(), brr.end());

	vector<int> result(N + M);

	int p1=0, p2=0, cm=0;

	while (p1 < N && p2 < M)
	{
		if (arr[p1] == brr[p2])
		{
			result[cm] = arr[p1];
			p1++;
			p2++;
			cm++;
		}
		else if (arr[p1] < brr[p2])
		{
			p1++;
		}
		else if (arr[p1] > brr[p2])
		{
			p2++;
		}
	}

	for (int i = 0; i < N + M; i++)
	{
		if (result[i] != 0)
		{
			cout << result[i] << " ";
		}
	}
}