교집합

두 집합 A, B가 주어지면 두 집합의 교집합을 출력하는 프로그램을 작성하세요.

입력설명
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
각 집합의 원소는 int형 변수의 크기를 넘지 않습니다.

출력설명
두 집합의 교집합을 오름차순 정렬하여 출력합니다.

입력예제 1
5
2 7 10 5 3
5
3 10 5 17 12

출력예제 1
3 5 10

 

이문제는 정적으로 배열을 할당받으면 메모리낭비도 심하고 동작시간이 1초가 넘어간다 따라서 동적배열을 할당하여 구현해야한다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void sort(vector<int> arr)
{
	int index;
	int tmp;
	for (int i = 0; i < 5; i++)
	{
		int min = 9999;
		for (int j = i; j < 5; j++)
		{
			if (min > arr[j])
			{
				min = arr[j];
				index = j;
			}
		}
		tmp = arr[i];
		arr[i] = arr[index];
		arr[index] = tmp;

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

int max(int a,int b) {
	if (a > b)
	{
		return a;
	}
	else
		return b;
}
int main(void)
{
	
	int count2 = 0;
	int result = 0;
	int N;
	int N2;
	int count = 0;
	cin >> N;
	vector<int> arr(N);
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	cin >> N2;
	vector<int> arr2(N2);
	for (int i = 0; i < N2; i++)
	{
		cin >> arr2[i];
	}
	result = max(N, N2);
	vector<int> results(result);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (arr[i] == arr2[j])
			{
				results[count2] = arr[i];
				count2++;
			}
		}
	}
	sort(results);

}

                                                          

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


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


	cin >> N2;
	vector<int> arr2(N2);
	for (int i = 0; i < N2; i++)
	{
		cin >> arr2[i];
	}
	sort(arr2.begin(),arr2.end());


	vector<int> arr3(N+N2);
	
	while (p1<N&&p2<N2)
	{
		if (arr[p1] == arr2[p2])
		{
			arr3[p3++] = arr[p1++];
			p2++;
		}
		else if (arr[p1] < arr2[p2])
		{
			p1++;
		}
		else
			p2++;

	}
		
	for (int i = 0; i < p3; i++)
	{
		cout << arr3[i];
	}
}

                                                           투포인트 알고리즘 방식