Two Pointer (C++)

투 포인터는 매우 쉽고 효율적인 테크닉으로, 일반적으로 소팅된 배열에서 검색하는 방법이다. 

주어진 배열 A(sorting in ascending order), 그리고 N integers 가 있다.(target값).

해당 배열에서 임시로 설정한 pair( A[i], A[j] ) 의 합이 target 과 같은 것이 있는지 찾는 것이다. 

예시를 보며 이해해보자. 

A[] = {10, 20, 35, 50, 75, 80}
X = =70
i = 0
j = 5

A[i] + A[j] = 10 + 80 = 90
Since A[i] + A[j] > X, j--
i = 0
j = 4

A[i] + A[j] = 10 + 75 = 85
Since A[i] + A[j] > X, j--
i = 0
j = 3

A[i] + A[j] = 10 + 50 = 60
Since A[i] + A[j] < X, i++
i = 1
j = 3
m
A[i] + A[j] = 20 + 50 = 70
Thus this signifies that Pair is Found.

X값이 70, 찾으려는 타겟 값이다. 하나의 포인터는 0부터, 다른 하나는 배열의 오른쪽 끝 부터 시작했다.

 

2가지 방법으로 Two pointer를 구현해보자. 

Method 1. Naive Approach using loops ( O(n^2) )

Method 2. Optimal approach using two pointer algorithm. 

 

Method 1. 

// Example program
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

bool isPairSum(int A[], int N, int X) {
    for(int i =0 ; i<N; i++) {
        for(int j = 0; j < N; j++) {
            // i == j means same element.
            if(i == j) continue;
            
            if( A[i] + A[j] == X) {
                printf("[%d][%d] \n", i, j);
                return true;
            }
            if( A[i] + A[j] > X) break;
        }
    }
    return false;
}


int main() {
    int arr[] = {2,3,5,8,9,10,11};
    int val = 17;
    int arrSize = sizeof(arr)/sizeof(int);
    sort(arr, arr+arrSize);
    cout << isPairSum(arr, arrSize, val) << '\n';
    return 0;
}

 

Method 2: REAL Two Pointers Technique.

Method 1은 그냥 모든 경우의 수를 다 searching 해서 찾는 것이고, 투 포인터로 풀면 좀 더 시간 복잡도를 줄일 수 있다.

bool isPairSum(int A[], int N, int X) {
    int i = 0; // left
    int j = N-1; // right
    
    while( i < j ) {
        if(A[i] + A[j] == X) {
            printf("[%d][%d]\n", i, j);
            return true;
        }
        if(A[i]+A[j] < X) {
            i++;
        } else if(A[i]+A[j] > X) {
            j--;
        }
    }
    
    return 0;
}

Time Complexity : O(nlogn) ( As sort function is used )

Auxiliary Space : O(1)

 

 

간단하게 LeetCode 에서 Two Pointer EASY - 문제를 풀어BOZA.

https://ding-dong-in-future.tistory.com/362

2000. Reverse Prefix of Word (C++)