알고리즘) Two Pointer, Sliding Window

Two Pointer

2개의 지점(포인터)을 옮겨가며 답을 구한다. 순차적 접근 등이 요구되는 특수한 상황에서 사용된다.
ex) 정렬된 두 배열을 하나의 정렬된 배열로 합칠 때(Merge Sort에서 사용됨), 어떤 배열의 연속 부분집합의 원소합이 k인 경우를 찾는 경우 등 ...

자세한 내용은 Merge Sort 부분 참고

---

Sliding Window

Two pointer와 비슷하지만, 두 포인터 사이의 길이가 고정되어있다는 차이가 있다.

Input	Output
첫 번째 줄에는 배열 D의 원소의 개수 N과 윈도우 사이즈 K 가 주어지고, 두 번째 줄에는 배열의 원소 Di가 주어집니다. (Di 는 자연수)	배열 D의 길이가 K인 연속부분집합의 원소 합의 최대값을 출력합니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        ArrayList<Integer> d = new ArrayList<>();
        for (int i = 0; i < n; i++)
            d.add(scanner.nextInt());

        int sum = 0, max = 0;
        for (int i = 0; i < n; i++) {
            if (i < k) sum += d.get(i);
            else sum = sum - d.get(i - k) + d.get(i);
            max = (max < sum) ? sum : max;
        }

        System.out.println(max);
    }
}