투 포인터와의 차이점

투 포인터의 성질

연속되고 + 가변적인 부분 배열을 활용

대표 유형

1. 2개의 포인터 변수 시작점이 배열의 시작점인 경우 (백준 #2018 수들의 합5)
2. 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우 (백준 #2467 용액)

시간복잡도

O(n) 의 시간복잡도를 가진다.

슬라이딩 윈도우

투 포인트와 마찬가지고 연속되는 부분 배열을 활용해 특정 조건을 일치시키는 알고리즘이지만,
고정적인 부분 배열의 크기를 가진다.

연속된, 고정적인 부분 배열을 활용해 특정 조건을 일치시키는 알고리즘.

관련 알고리즘 문제

백준 #10025: 게으른 백곰

문제링크

// 슬라이딩 윈도우: 윈도우 크기에 주의하자

package solution;

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

public class BOJ10025_게으른백곰 {
    static int N, K;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        //크기가 고정적 : K
        //배열안의 연속적인 수의 합을 구함
        // 슬라이딩 윈도우
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[1000001];
        int gram, pos;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            gram = Integer.parseInt(st.nextToken());
            pos = Integer.parseInt(st.nextToken());
            arr[pos] = gram;

        }
        int size = 2*K+1;
        int sum=0;
        for (int i = 0; i < ((size<=arr.length)? size : arr.length); i++) {
            sum += arr[i];
        }
        int max = sum;
        for (int i = size; i < arr.length; i++) {
            sum = sum - arr[i-size] + arr[i];
            max = Math.max(max, sum);
        }
        System.out.println(max);
    }
}

윈도우 크기가 배열의 크기보다 클 수도 있게 주어지는 문제라 배열인덱스초과에 유의하여야 한다