투포인터 (Two Pointers)

투포인터 알고리즘 (Two Pointers)

• 리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어 있는 두 리스트의 합집합에도 사용된다. 
• 병합 정렬에 쓰임

투포인터 알고리즘의 대표 유형 - 특정한 합을 가지는 부분 연속 수열 찾기

• 어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제

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

투 포인터 알고리즘 구현하기

int n = 5 //데이터 개수 N
int m = 5 //찾고자 하는 부분합 M

int count = 0;
int interval_sum = 0;
int start = 0;
int end = 0;

//start를 차례대로 증가시키며 반복
while(start < n) {
    //end만큼 이동시키기
    while(interval_sum < m && end < n) {
    	interval_sum += data[end];
        end++;
    }
    //부분합이 M일때 카운트 증가
    if(interval_sum == m) {
    	count++;
    }
    interval_sum -= data[start];   
    start++;
}

System.out.println(count);

투 포인터의 시간복잡도는 O(N)

• 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고, 각 포인터가 n번 누적 증가해야 알고리즘이 끝난다.
  • 각각 배열 끝에 다다르는데 O(N)이라 둘을 합해도 여전히 O(N)이다.

 

[Algorithm] 투포인터(Two Pointer) 알고리즘