[java] 투 포인터(Two Pointers)

투 포인터(Two Pointers)란?

: 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법

  다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다.

 

- 두 개 포인터의 배치방법

1) 같은 방향에서 시작 : 첫번째  원소에 둘 다 배치

2) 서로 다른 뱡향에서 시작 : 첫번째 원소와 마지막 원소에 배치

 

---

투 포인터 예시 : 배열에서 부분합이 9가 되는 구간을 찾는 방법

 - 기존 단순 for문 이용방법

기존 for문 이용방법

[단순 for문 이용방법 - 코드로 봤을 때]

import java.util.Arrays;

public class Main {
   public static int[] forLoop(int[] arr, int target){ // for문을 이용한 방법
      int[] result = {-1, -1}; // 구간으로 출력해줄 result 초기화

      for (int i = 0; i < arr.length ; i++) {
         int sum = arr[i]; //부분합을 계산해줄 변수 초기화
         for (int j = i + 1; j < arr.length ; j++) {
            if (sum == target) { // 만약 sum값이 target값(찾는 값) 하고 같으면
               result[0] = i;
               result[1] = j - 1;
               break; // 두번째 for문 탈출
            }
            sum += arr[j];
         }

         if (sum == target){
            break; // 첫번째 for문 탈출
         }
      }
      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))); // 찾는 값이 9일때 _ 결과 값 : {4, 5} → 배열값에서 7 + 2 = 9
      System.out.println(Arrays.toString(forLoop(arr, 14))); // 찾는 값이 11일때 _ 결과 값 : { -1, -1} → 부분합을 구할수 있는 부분이 없음
   }
}

 

---

- 투포인터 이용방법

투 포인터 이용방법

:

1. 부분합이 찾는 부분합보다 작으면 pointer 1을 이동시킴 (1 → 2(합 : 3) → 5 (합 : 8) → 3(합 : 11 )

이때 3까지 가면 합이 11이니까 pointer 1은 거기서 멈춘상태( 합이 9보다 큼)

 

2. 현재상태가 찾는 부분합보다 크면 pointer 2를 이동시킴(1 → 2(합 : 10) → 5(합 : 8))

 

3. 이 때, 현재상태가 찾는 부분합보다 작으니까 다시 pointer 1이동 

.

.

. 이런식으로 진행된다.

 

 

[투포인터 이용방법 - 코드로 봤을 때]

import java.util.Arrays;

public class Main {

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

      while (true){ // 반복문을 돌리면서
         if (sum > target){ // 합이 찾는 값보다 크면
            sum -= arr[pointer2++]; // 포인터2를 증가시키면서 빼주고
         } else if (pointer1 == arr.length) { // 만약 포인터 1가 끝까지 도달했을땐
            break; // 탈출(sum값을 못찾았다는 뜻이기때문)
         } else { // 그외에는
            sum += arr[pointer1++]; // 포인터 1을 증가시키면서 더해준다
         }
         if (sum == target){
            result[0] = pointer2;
            result[1] = pointer1 -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(twoPointers(arr,9))); // 찾는 값이 9일때 _ 결과 값 : {4, 5}
      System.out.println(Arrays.toString(twoPointers(arr, 14))); // 찾는 값이 11일때 _ 결과 값 : { -1, -1}
   }
}

 

---

<<투포인터 활용문제>>

[백준] 문제번호 3273 (두 수의 합)(java) (tistory.com)

[백준] 문제번호 3273 (두 수의 합)(java)