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

투 포인터 알고리즘

리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘

만약 투 포인터 알고리즘을 사용하지 않으면, 이중 반복문 때문에 시간 복잡도가 O(n^2)이 된다.
그러나 투 포인터 알고리즘을 사용하면 O(N)으로 줄일 수 있음

투 포인터 알고리즘은 크게 아래 두가지로 나눌 수 있다.

1. 두 포인터가 같은 방향으로 진행하는 방법
2. 두 포인터가 다른 방향으로 진행하는 방법

각각의 예제는 아래와 같다.

예제1) 특정한 합을 가지는 연속 부분 수열 찾기

• 음수데이터가 있으면 투포인터 알고리즘 사용이 불가능하다.
• 로직

1. start, end를 첫번째 원소를 가리키도록 한다.
2. 현재 부분합이 M과 같다면 카운트 
3. 현재 부분합이 M보다 작으면 end 1증가.
4. 현재 부분합이 M보다 크거나 같으면 start 1증가.
5. 모든 경우 확인할 때까지 반복

• 코드

int low = 0;
int high = 0;
int sum = 0;
int cnt = 0;
while(low < N) {
	if (sum == M) {
    	cnt++;
        sum -= arr[low++];
    } else if (sum > M || high == N) 
    	sum -= arr[low++];
    else 
    	sum += arr[high++];
}	
return cnt;

예제2) 배열의 두 원소의 합이 특정값을 가지는 경우의 수 찾기

• 배열이 정렬된 상태에서만 사용 가능하다.
• 로직

1. start = 0, end = N-1 을 가리키도록 한다.
2. 합이 M보다 크다면 end포인터를 감소시킴
3. 합이 M보다 작다면 start포인터를 증가시킴
4. 합이 M이면 arr[start]와 동일한 값을 가지는 연속하는 값 개수(cnt1),
arr[end]와 동일한 값을 가지는 연속하는 값 개수(cnt2)를 곱해서 cnt에 더해줌.
5. start < end를 만족할 때까지 위 과정을 반복한다. 

• 코드

long result = 0;
int s = 0, e = arr.length -1;

while(s < e) {
	long sum = arr[s] + arr[e];
    if (sum == X) {
    	int a = arr[s];
        int b = arr[e];
       	long acnt = 0, bcnt = 0;
        while(s < arr.length && arr[s] == a) {
        	s++;
            acnt++;
        }
        while(e >= 0 && arr[e] == b) {
        	e--;
            bcnt++;
        }
        result += acnt * bcnt;
    }
    else if (sum > X)
  		e--;
    else if (sum > X)
    	s++;
}

return cnt;