알고리즘 - 투 포인터

투 포인터(Two pointers) 란?

배열이나 리스트에서 두 개의 포인터를 이용하여 원하는 결과를 찾거나 주건을 만족하는 부분을 찾는 알고리즘 기법. 주로 정렬된 배열에서 특정 합을 갖는 부분 배열을 찾거나, 두 요소의 합이 특정 값과 같은지 검사하는 문제에 많이 사용됨.
이 기법은 대개 배열을 한 번만 순회하므로 시간복잡도가 O(N) 으로 매우 효율적임

import java.util.Arrays;

public class Main {
    public static int[] forLoop(int[] arr, int target) {
        int[] result = {-1, -1};

        for (int i = 0; i < arr.length; i++) {
            int sum = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (sum == target) {
                    result[0] = i;
                    result[1] = j - 1;
                    break;
                }
                sum += arr[j];
            }
            if (sum == target) {
                break;
            }
        }
        return result;
    }

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

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 3, 7, 2, 4, 3, 2};
        System.out.println(Arrays.toString(forLoop(arr, 9)));
        System.out.println(Arrays.toString(forLoop(arr, 14)));
        System.out.println();

        System.out.println(Arrays.toString(twoPointers(arr, 9)));
        System.out.println(Arrays.toString(twoPointers(arr, 14)));
    }
}

forLoop 메서드

1. 첫 번째 for-loop 는 부분 배열의 시작 인덱스를 나타냄
2. 두 번째 for-loop 는 부분 배열의 끝 인덱스를 나타냄
3. 내부 루프에서 부분 배열의 합을 계산
4. 합이 target과 같다면 그 부분 배열의 시작과 끝 인덱스를 결과로 반환

twoPointers 메서드

1. p1 과 p2는 부분 배열의 시작과 끝을 나타냄
2. sum은 현재 부분 배열의 합을 저장
3. sum이 target보다 크면 p1을 오른쪽으로 이동시켜 합을 줄임
4. p2가 배열의 끝에 도달하면 루프를 종료
5. sum이 target보다 작으면 p2를 오른쪽으로 이동시켜 합을 증가
6. sum이 target과 같으면 그 부분 배열의 시작과 끝 인덱스를 결과로 반환