투 포인터(Two Pointers)

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘.

• 정렬되어 있는 두 리스트의 합집합에도 사용된다
• 병합정렬의 conquer 영역의 기초가 되기도 한다

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

step 1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리킨다
step 2. 구하고자 하는 M값과 현재 부분합 S 가 같다면 카운트한다.
step 3-1. S < M 일때 끝점 end를 1 증가시킨다.
step 3-2. 아니라면 시작점 start를 1 증가시킨다.
step 4. 모든 경우를 확인할 때까지 2~3번을 반복한다.

시간복잡도: O(n)

[BOJ]2018. 수들의 합5

문제링크

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

public class BOJ2018_수들의합5 {
    static int N, start, end, sum, cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 투포인터
        start=1;
        end=1;
        sum=1;

        while(true) {
            if (sum == N) cnt++;    // sum=N이 나올때마다 카운트

            //기저조건
            if (start == end && start == N) break;

            if (sum < N) {
                end++;          //끝점 다음칸으로 이동시키고 합을 더한다
                sum += end;
            } else {
                sum -= start;   //시작점을 다음칸으로 이동시키는데, 먼저 현재start 빼고나서  start 증가 시킨다
                start++;
            }
        }
        System.out.println(cnt);
    }
}

비슷한 개념: 슬라이딩 윈도우