[Algorithm] 교집합(투포인트 알고리즘) (MS interview source)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 두 집합의 교집합을 오름차순 정렬하여 출력하라..!

     우선 최대 N이 30,000 이니까 최악의 경우 900,000,000 이므로

     그냥 풀 문제는 아닌 것 같다.

     2 7 10 5 3

     3 10 5 17 12

     우선 정렬을 안 하고 이 문제를 풀 수 있을지 생각해보자.

     정렬을 안 한 상태로 O(N^2)이 나올텐데..

     정렬을 한 상태로 문제에 접근해보자.

     최근에 풀어본 선택정렬을 적용해서 정렬을 해보았다.

     p1 = 0, p2 = 0,

     두 개의 포인터 변수가 n1 혹은 n2 보다 작을 때까지 반복한다.(작은 배열을 모두 탐색했을 경우 종료되도록)

     2 3 5 7 10

     3 5 10 12 17

     첫 번째 배열 기준으로 동작해보면

     2는 3보다 작으므로 p1++

     2 3 5 7 10

     3 5 10 12 17

     같은 숫자를 발견했다 ! print(p1), p1++, p2++

     2 3 5 7 10

     3 5 10 12 17

     같은 숫자를 발견했다 ! print(p1), p1++, p2++

     2 3 5 7 10

     3 5 10 12 17

     7은 10보다 작으므로 p1++

      2 3 5 7 10

      3 5 10 12 17

     같은 숫자를 발견했다 ! print(p1), p1++, p2++

     여기서 p1 = n1 이 될 것이다.

     그러면 while 문을 종료하면 된다.

 

     이제 코드로 옮겨보자~!

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void insertionSort(vector<int>& v, int n)
{
    int i, j, key;
 
    for (i = 1; i < n; i++)
    {
        j = i - 1;
        key = v[i];
 
        while (j >= 0 && v[j] > key)
        {
            v[j + 1] = v[j];
            j--;
        }
 
        v[j + 1] = key;
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int an, bn, ap = 0, bp = 0, i;
 
    scanf("%d", &an);
    vector<int> a(an);
    for (i = 0; i < an; i++)
        scanf("%d", &a[i]);
 
    insertionSort(a, an);
 
    scanf("%d", &bn);
    vector<int> b(bn);
    for (i = 0; i < bn; i++)
        scanf("%d", &b[i]);
 
    insertionSort(b, bn);
 
    while (ap < an && bp < bn)
    {
        if (a[ap] == b[bp])
        {
            printf("%d ", a[ap]);
            ap++, bp++;
        }
        else if (a[ap] < b[bp])
            ap++;
        else
            bp++;
    }
 
    puts("");
 
    return 0;
}

#. Other code

#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(m), c(m);
    for(i=0; i<m; i++)
        scanf("%d", &b[i]);
 
    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;
}

로직은 같다. 다만 std 에서 제공하는 정렬 함수 sort 를 사용하셨다.

굳이 정렬 함수를 만들어서 했나 싶기도 하다..꺌꺌

#. Result

  - Input --------------------------------------------------------

5

2 7 10 5 3

5

3 10 5 17 12

------------------------------------------------------------------

  - Output --------------------------------------------------------

3 5 10

------------------------------------------------------------------