Goal

투포인트 알고리즘을 이용해서 두 배열의 교집합을 찾을 수 있다.

문제

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

입력설명

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어진다.
두 번째 줄에 N개의 원소가 주어진다.(중복 X)
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어진다.
네 번째 줄에 집한 M개의 원소가 주어진다. (중복X)

출력설명

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

예제

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

출력
3 5 10

풀이

 일반적으로 생각할 수 있는 풀이방법은, 첫번째 배열 A에서 원소한개를 지정하고, 두번째 배열 B에서 같은 값이 있는지 확인을 한다. 첫번째 배열의 마지막값 까지 두번째 배열에서 같은값이 있는지 확인해서 교집합을 찾아내는 방법이 있다.

 하지만 문제에서 배열의 최대 크기가 30,000이기 때문에 배열의 크기가 증가함에 따라 1초이상의 처리시간이 걸린다.

  알고리즘의 시간 효율을 높이기 위해서는 투포인트 알고리즘을 적용하면 된다.

투포인트 알고리즘 이란?
각자 다른원소를 가리키고 있는 포인트를 조작하여 원하는 결과값을 찾아내는 알고리즘 이다.

  1. a 배열 : [2 7 10 5 3], b 배열 : [3 10 5 17 12]이 입력 되었으면, 두 배열을 오름차순으로 정렬 한다.

    a 배열 : 2 3 5 7 10
    b 배열 : 3 5 10 17 12

  2. a배열의 0번째 값과 b배열의 0번째 값이 같으면 교집합이므로, c배열에 값을 추가 시킨다.

  3. a배열의 index, b배열의 index값을 모두 1씩 증가시키고, 교집합 C의 원소에도 1개가 추가된것이니 C의 index값도 증가 시킨다.

  4. a배열의 0번째 값이 b배열의 0번째 값보다 작으면, b배열에는 절대로 a배열의 0번째 값이 존재하지 않는다.(a,b배열은 오름차순으로 정렬되어 있으므로)

  5. a배열의 index값을 증가시켜서 포인트를 이동시킨다.

  6. a배열의 첫번째 값과, b배열의 0번째 값을 비교

  7. 2~6 반복

  8. 배열 a,b중 하나라도 배열을 한번 순회 했다면 교집합이 모두 찾아진것 이다.

#include <stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main() {

    int n,m,i,p1=0,p2=0,p3=0;
    scanf("%d",&n);
    vector<int> a(n);
    for(i = 0; i < n; i++) scanf("%d",&a[i]);
    sort(a.begin(),a.end());
    scanf("%d",&m);
    vector<int> b(n);
    for(i = 0; i < m; i++) scanf("%d",&b[i]);
    sort(b.begin(),b.end());
    vector<int> c(n+m);

    while(p1 < n && p2 < m) {
        if(a[p1] < b[p2]) {
            p1++;
        } else if(a[p1] > b[p2]) {
            p2++;

        } else if(a[p1] == b[p2]) {
            c[p3] = a[p1];
            p1++;
            p2++;
            p3++;
        }
    }
    for(i = 0; i < p3; i++) {
        printf("%d ",c[i]);
    }
    return 0;
}