[알고리즘] 투 포인터

유튜브 강의를 보고 작성한 글입니다.

투포인터

- 투포인터 기법

• 두 개의 포인터를 만들어서
• 각각이 가리키는 원소에 의미 부여해
• 요구하는 문제 해결

- 특징

• 많은 경우에 O(N^2)를 O(N)으로 떨어트림
• 포인터에 의미를 부여하는 작업에 대한 예시들을 다양하게 접해봐야 함
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있음
  

- 대표적인 예시

1) 포인터 2개가 같은 방향으로 진행해 나아가는 것
2) 포인터 2개가 양끝에서 반대로 진행하는 것
3) 포인터 하나는 한쪽 방향으로만 진행, 다른 포인터는 양쪽으로 이동

관련 문제 및 응용 방법

특정한 합을 가지는 부분 연속 수열 찾기

• 완전 탐색 이용 시 O(N^2) 수행시간
• 투 포인터 활용 시
  1) 시작점(start)과 끝점(end)이 첫번째 원소의 인덱스를 가리키도록
  2) 현재 부분 합이 M과 같다면, 카운트
  3) 현재 부분 합이 M보다 작으면 end 1 증가
  4) 현재 부분 합이 M보다 크거나 같으면 start를 1 증가
  5) 모든 경우를 확인할 때 까지 2번부터 4번까지의 과정 반복
  

수들의 합2(BOJ 2003번)

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class numSum_2003 {



    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n= Integer.parseInt(st.nextToken());
        int m= Integer.parseInt(st.nextToken());

        int[] arr = new int[n];

        st = new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }


        int end = 0;
        int sum = 0;
        int count = 0;

        for(int i=0;i<n;i++){
            //끝나는 포인터 밀기
            while(sum<m && end<n){
                sum += arr[end];
                end++;
            }
            if(sum == m){
                count++;
            }
            //시작포인터 밀기
            sum -= arr[i];
        }

        System.out.println(count);

    }
}