40. 투포인터 알고리즘

처음 작성했던 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    //	freopen("input.txt", "rt", stdin);
    int n, m, i, p1 = 0, p2 = 0, p3 = 0, tmp = 0, j, midx = 0;

    scanf("%d", &n);
    vector<int> a(n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &m);
    vector<int> b(m);
    for (i = 0; i < m; i++)
        scanf("%d", &b[i]);

    vector<int> c(m > n ? m : n);

    while (p1 <= n)
    {
        for (i = 0; i < m; i++)
        {
            if (a[p1] == b[i])
            {
                c[p3++] = b[i];
                break;
            }
        }
        p1++;
    }

    for (i = 0; i < p3; i++)
    {
        tmp = c[i];
        midx = i;
        for (j = i; j < p3; j++)
        {
            if (c[j] < c[midx])
                midx = j;
        }
        c[i] = c[midx];
        c[midx] = tmp;
    }

    for (i = 0; i < p3; i++)
        printf("%d ", c[i]);

    return 0;
}

 

개선할 점

1. a 배열과 b 배열을 비교하는 방식의 시간 복잡도가 이중for문을 사용하는 방식, n^2과 다를바 없음.
2. 배열을 선택정렬로 정렬하여 시간 복잡도가 n^2임.
3. 1, 2, 3번 테스트 케이스 통과, 4번 테스트 케이스에서 오답이 나옴. 5번 테스트 케이스 시간 초과(n=30,000). 

 

투포인터 알고리즘

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    //	freopen("input.txt", "rt", stdin);
    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]);

    scanf("%d", &m);
    vector<int> b(m);
    for (i = 0; i < m; i++)
        scanf("%d", &b[i]);

    vector<int> c(m > n ? m : n);

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    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++)
        printf("%d ", c[i]);

    return 0;
}

 

1. a 배열과 b 배열을 먼저 오름차순으로 sort하여 p1, p2 포인터(int* 포인터가아니라 인덱스를 저장하는 포인터이다.)로 각 배열을 비교하여 교집합을 찾는다.
2. 시간복잡도가 n
3. algorithm헤더의 퀵정렬방식의 sort 함수를 사용하였음. (nlogn)