[C++] 투 포인터

정의

투포인터란 포인터 2개를 조작하여 원하는 결과를 얻는 방법이다

• 무식하게 for문을 사용하면 O(N^2)이지만 투 포인터는 O(N)

구간 용어
폐구간	이상~이하	[ ]
개구간	초과~미만	( )
반개구간	초과~이하	( ]
	이상~미만	[ )

 

같은 방향의 투 포인터

• 주로 구간의 경우의 수를 구하는데 사용한다
• 배열의 원소가 모두 자연수여야 한다
  • 배열이 정렬 되어 있지 않아도 된다.

알고리즘 원리
초기 상태	포인터 2개 모두 출발점
종료 조건	종료 포인터가 끝에 도달할 때까지 알고리즘 반복
동작	구간 합이 목표보다 작으면 종료 포인터 전진 구간 합이 목표보다 크거나 같으면 시작 포인터 전진

 

예시코드 (백준 2003번)

int arr[1001];

// 구간합 경우의 수 구하기
int twoPoint(int n, int k) { // 원소 수, 목표
    int sum = 0, ret = 0;
    int st = 0, en = 0;

    while(en < n) {
        sum += arr[en++];
        
        while(sum >= k) {
            if(sum == k) ans++;

            sum -= arr[st++];
        }
    }
    
    return ret;
}

 

다른 방향의 투 포인터

• 두 원소의 경우의 수를 구할 때 사용할 수 있다.
• 배열이 1개 또는 2개일 때 사용한다.
• 음수가 있어도 된다.
• 배열의 원소가 정렬 되어 있어야 한다.

알고리즘 원리
초기 상태		시작 포인터는 0,  종료 포인터는 N-1
종료 조건	배열 1개	시작 포인터가 종료 포인터보다 작을 때까지 반복
	배열 2개	시작 포인터가 도착점보다 작고, 종료 포인터가 출발점보다 같거나 클 때까지 반복
동작		두 원소의 연산이 목표보다 작으면 포인터 전진 도 원소의 연산이 목표보다 크면 포인터 전진

 

예시 코드 (백준 7453번)

// 두 원소의 합 경우의 수 구하기

int A[101], B[101];

int twoPoint(int n, int k) {
    int ans = 0;
    int st = 0, en = n - 1;

    sort(A, A + n);
    sort(B, B + n);

    // while(st < en) {   // 배열 1개
    while(st < n && en >= 0) {   // 배열 2개
        if(A[st] + B[en] == k) {
            int ai = 0, bi = 0;
            
            // 중복된 것을 더하기
            while(st + ai < n && A[st] == A[st + ai])
                ai++;
            while(en - bi >= 0 && B[en] == B[en - bi])
                bi++;
                
            ans += ai * bi;
            st += ai;
            en -= bi;
        }
        else if(A[st] + B[en] > k) 
        	en--;
        else 
        	st++;
    }
    
    return ans;
}