TwoPoint

투 포인터

투 포인터 알고리즘은 연속되는 숫자의 합을 구할때 등, 시간 복잡도를 최적화 시켜주는 알고리즘 입니다.

이 알고리즘은, N개의 숫자가 존재할 때, 연속되는 합이 5인 경우의 갯수를 센다고 가정한다고 하면,

start 와 end point를 생성하고 변수 sum을 만들어줍니다.

그런 다음 조건문을 만들어줍니다.

sum < N = ture이면,

sum += end_point를 해주고, end_point++를 해줍니다.

sum > N = ture이면,

sum -= start_point를 해주고, start_pint++를 해줍니다

sum == N을 만족하면,

end_point++를 해주고

sum += end_point와

count ++ ( 경우의 수 )

을 해주면 됩니다.

이렇게 해주면 투 포인터 알고리즘이 완성됩니다.

예시 코드 [ 백준 2018번 문제 ]

import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
						//입력 값 N = 15
            Scanner in = new Scanner(System.in);
            int size = in.nextInt();
            int count = 1;
            int start = 0;
            int end = 0;
            int sum = 1;
            int[] dataList = new int[size];
            for (int i = 0; i < size; i++) {
                dataList[i] = i + 1;
            }

            while (end < size - 1) {
                if (sum < size) {
                    end++;
                    sum += dataList[end];
                } else if (sum > size) {
                    sum -= dataList[start];
                    start++;
                } else {
                    end++;
                    sum += dataList[end];
                    count++;
                }
            }
            System.out.println(count);
        }
    }