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

  투 포인터(Two Pointer)란 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘입니다. 포인터는 첫 번째 원소에 둘 다 배치하여 같은 방향에서 시작하는 방법과 각각 첫 번째 원소와 마지막 원소에 배치하여 서로 다른 방향에서 시작하는 방법이 있습니다. 이를 이용하여 다중 for문의 복잡도를 줄일 수 있습니다.

 

  투 포인터 구현 코드(첫 번째 원소에서 시작)

public static int[] twoPointers(int[] array, int target) {
    int p1 = 0;
    int p2 = 0;
    int sum = 0;
    int[] result = {-1, -1};

    while (true) {
        if (sum > target) {
            sum -= array[p1++];
        } else if (p2 == array.length) {
            break;
        } else {
            sum += array[p2++];
        }
        if (sum == target) {
            result[0] = p1;
            result[1] = p2 - 1;
            break;
        }
    }
    return result;
}

  이 코드는 주어진 배열에서 부분합이 target이 되는 구간을 찾는 방법입니다. 문제의 내용에 따라 그에 맞는 식의 변형이 필요합니다.

  포인터의 위치 p1과 p2를 생성합니다.

  부분합을 담을 sum 변수를 생성합니다.

 부분합의 구간을 담을 result 변수를 생성합니다. 각 원소를 -1로 초기화합니다.

  while문이 참일 때 반복합니다.

  첫 번째 if문에서 sum이 target보다 클 때 sum에서 array의 p1 번째 원소를 뺍니다.

  else if에서 p2가 주어진 배열의 끝에 닿았을 때 break를 이용하여 반복문을 종료합니다.

  앞선 조건에 해당하지 않으면 array의 p2 번째 원소를 sum에 더해줍니다.

  if문에서 sum이 target과 같다면 result의 0 번째 인덱스에 p1을, result의 1번째 인덱스에는 p2 - 1을 할당합니다. 원하는 값을 구했으므로 break를 이용하여 반복문을 종료합니다.

 

  이 코드에서는 두 개의 포인터를 모두 첫 번째 원소 위치에 배치했습니다. 두 포인터 모두 같은 방향으로 이동합니다. p2가 먼저 이동하고 이동한 자리에 있는 원소를 더해주는 것입니다. 그러나 부분합이 원하는 값보다 커진다면 p1을 움직이고, p1에서 원래(움직이기 이전) 값은 부분합에서 제외해야 하므로 빼주는 것입니다.

  각 포인터의 위치를 처음과 마지막에 배치하는 코드도 이와 유사합니다. 다만, 포인터의 진행 방향이 서로 반대로 움직인다는 차이점이 있습니다.