투 포인터

특징

• 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법
• 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다
• 두 개 포인터의 배치 방법
  1) 같은 방향에서 시작
  - 첫 번째 원소에 둘 다 배치
  - 주어지는 조건에 따라서 2개의 포인터가 서로 다르게 움직임
  2) 서로 다른 방향에서 시작
  - 첫 번째 원소와 마지막 원소에 배치
  - 양쪽에서 서로 시작하여 만나는 과정에서 원하는 값을 구하는 방법

사용 예시

• 배열에서 부분합이 9가 되는 구간을 찾는 방법
  1) 단순 for문 사용
  
  2) 투포인터 방법
  

소스코드

// for-loop vs two pointers
//원하는 부분 합이 나오는 구간 구하기

import java.util.Arrays;

public class Main {

    //for문을 사용해서 구현
    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;  //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){   // 합계가 target 보다 작으면 p1 포인터 이동
                // 합계가 target 보다 작은데, p1이 끝에 도달해있으면 원하는 값을 가지는 구간합 없음
                if(p1 == arr.length){
                    break;
                }
                sum += arr[p1++];
            }else{  //합계가 target보다 크면 p2 포인터 이동
                sum -= arr[p2++];
            }

            // 합계가 target 과 같을 때 해당 구간 업데이트 후 반환
            if (sum == target) {
                result[0] = p2;
                result[1] = p1 - 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)));
    }
}