[C++] 투포인터 알고리즘

기초 문제

#include <iostream>
#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+1);
    
    for (i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }
    
    sort(a.begin(), a.end());//퀵정렬
    
    scanf("%d",&m);
    vector<int> b(m+1);
    for (i = 1; 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]) {
            c[p3++] = a[p1];
            p1++;
            p2++;
        }
        else if(a[p1] < b[p2]) p1++;
        else p2++;
    }
    
    for (i = 1; i < p3; i++) {
        printf("%d",c[i]);
    }
    
    return 0;
}

• 여러 배열의 인덱스를 별도로 증가시켜 하나하나 비교해야하는 경우 투포인터 알고리즘을 이용해야 한다.
• 두 배열의 인덱스를 가리키는 포인터 변수를 조건에 맞게 증가시키는 방식이다.
• 여기서는 크기 비교를 통해 포인터를 증가시키는데, (같으면 둘다 증가 작으면 작은쪽 증가 크면 큰쪽 증가)
• 두 배열이 정렬되어 있지 않으면 포인터를 다시 0부터 다시 탐색해나가야 한다.
• 정렬을 하게되어 2 3 5  3 5 7 이렇게 있다면
• a[p1] == 2 이고 b[p2] == 3이다. 더 작은 p1이 ++된다.
• 2는 더이상 비교할 필요가 없는 수이기 때문에 이대로 계속 진행해도 상관이 없게된다.

응용 문제

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N,i,p2=1,p3=1,p5=1, min = 2147000000;
    scanf("%d",&N);
    vector<int> UN(N+1);//Ugly Number
    
    UN[1] = 1;
    
    for(i = 2; i <= N; i++){
        
        //세 포인터 비교
        if(UN[p2]*2 < UN[p3]*3) min = UN[p2]*2;
        else min = UN[p3]*3;
        
        if(UN[p5]*5 < min) min = UN[p5]*5;
        
        //결과
        if(UN[p2]*2 == min) p2++;
        if(UN[p3]*3 == min) p3++;
        if(UN[p5]*5 == min) p5++;
        
        UN[i] = min;
    }
    printf("%d\n",UN[N]);
    
    return 0;
}

• 소인수 분해는 배수로 장난치는 문제들이 대부분이다.
• 배열은 하나이지만, 하나의 배열 안에서 2의 배수이거나 3의 배수이거나 5의 배수인 값에 대한 인덱스 간의 비교가 이루어지므로
• 이 문제는 세가지 포인터로 해결해야 하는 문제이다.
• 일단 Agly number를 저장할 배열에 for문을 돌리면서 index에 값을 할당해주어야 한다.
• 그럼 해당 index에는 어떤 값을 넣어줄까?
• 일단 2 혹은 3 혹은 5를 소인수로 가진 값들은 2의 배수 혹은 3의 배수 혹은 5의 배수인 값들이다.
• 이 값들 중에서 작은 값이 해당 인덱스에 들어가는 것이다
• 예를 들어, UN[2]에는 1*2 , 1*3, 1*5 중 가장 작은 값인 2가 들어갈 것이다.
• 조심해야 할 것은 3*2, 2*3처럼 동일 한 값이 있을 수도 있기 때문에, 이러한 경우 두 포인터를 동시에 모두 증가시켜주어야 한다.
• 따라서 if else가 아닌 if문을 세 줄로 하여 모두 증가시켜주도록 한다.

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