투포인트알고리즘

개념

투포인트 알고리즘이란 말 그대로 두개의 포인터를 사용하는 알고리즘이다. 물론 두개 이상도 가능하다. 한가지 예로 들면 두개의 길이가 다른 배열이 있을 때, 이 배열들을 서로 비교하면서 무엇인가를 하고 싶을때 사용하면 효과적이다.

밑에 코드는 그냥 다음의 문제를 풀 때 투포인트 알고리즘을 사용하는 것을 보여주는 것이다.
n = 5, m = 4
2 7 10 5 3
3 17 5 10
위와 같은 무작위로 정렬된 서로다른 두 배열의 교집합을 구해보자.

코드

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

#define instructor


int main()
{

    int n = 0, m=0,posA=0, posB=0;
    scanf("%d",&n);
    vector<int> a(n);
    for(int i=0; i<n; i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    vector<int> b(m);
    for(int i=0; i<m; i++){
        scanf("%d",&b[i]);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    //먼저 두 배열을 초기화 하는 과정이다. 
    vector<int> answer;
    // 이후 두개의 point인 posA와 posB에 따라 값을 넣어준다.
    while(posA <= n && posB <=m){
        if(a[posA]==b[posB]){
        // 두 값이 같은 경우 우리가 찾는 교집합이기 때문에 이를 answer vector에다 넣고 각 point들을 한칸씩 이동시킨다.
            answer.push_back(a[posA]);
            posA++;
            posB++;
        }
        /// 밑에 두 조건문은 point에 따른 원소에 값에 따라 point를 이동시키는 것 
        else if(a[posA]>b[posB]) posB++;
        else posA++;
    }

    for(int i=0; i<answer.size(); i++) printf("%d\n",answer[i]);

    return 0;
}

시간복잡도

위의 정렬 방법의 시간복잡도는 sort() 함수가 퀵 솔트로 만들어 진것이므로 O(nlogn)이다. 그러나 이미 정렬된 배열일 경우 시간복잡도는 O(n)으로 매우 효율적인 알고리즘이다.