[알고리즘 연습] 교집합(투포인터 알고리즘) (by. C++)

교집합(투포인터 알고리즘)

• 정수 N을 입력받고 N개의 정수를 입력받는다. (집합A)
• 정수 M을 입력받고 M개의 정수를 입력받는다. (집합B)
• 집합A와 집합B의 교집합을 오름차순으로 정렬하여 출력하시오.

---

풀이

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

int main() {
    int n, m, i, p1=0, p2=0, p3=0;

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

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

    vector<int> c(m+n);

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

    for(i=0; i<p3; i++) {
        cout << c[i] << " ";
    }    

    return 0;
}

• 투포인터 알고리즘을 활용한다. (포인터 2개를 활용)
• 입력받은 집합 둘 모두 정렬된 상태로 만든다
• 2개의 포인터를 활용해 각 집합의 요소를 비교해가며 작은 숫자를 가진 집합의 포인터를 증가시킨다.
• 같으면 교집합으로 체크하여 넣고, 두 집합 모두의 포인터를 증가시킨다.
• 두 포인터 중 하나라도 끝에 이르면 종료한다.
• cf. sort(a.begin(), a.end())는 algorithm에 존재하는 내장메소드로, vector에 대해 퀵정렬을 수행한다.