[자료구조]슬라이딩 윈도우 With 투 포인터

참고 : https://deergum.github.io/algorithm/algorithm-BJ10025/

 

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결하는 알고리즘입니다. 부분 배열들을 활용해 특정 조건을 일치시키는 알고리즘이라는 점을 놓고 보면 투 포인터 알고리즘이랑 거의 유사한 방식입니다. 다만 부분 배열의 길이(크기)가 고정적이기 때문에 가변적인 배열의 길이(크기)를 가질 수 있는 투 포인터 알고리즘과는 좀 다릅니다. 창문을 왼쪽부터 오른쪽으로 밀면서 창문 안에 있는 값들을 부분 배열이라고 생각하시면 됩니다.

 

또 다른 차이점은 투 포인터 알고리즘은 부분 배열의 길이가 가변적이기에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요한 반면, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 잡기에 포인터 변수가 2개일 필요가 없다는 것입니다. 고정적인 부분 배열의 크기를 나타내는 변수가 있을 경우 포인터 하나만 있어도 부분 배열 크기를 알고 있기에 각 배열의 끝이 어딘지 알 수 있습니다.

 

주황색 칸이 3의 고정 길이를 가지는 부분 배열이라고 가정하겠습니다. 만약 부분 배열의 합을 구하는 문제일 때, 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에는 겹치는 부분이 존재합니다. 즉, 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가해주시면 됩니다.

○ 예제

백준 10025번 - 게으른 백곰

https://www.acmicpc.net/problem/10025

10025번: 게으른 백곰

*문제풀이

슬라이딩 윈도우 알고리즘으로 풀기 위해 윈도우를 처음에 지정한 다음 한칸씩 옆으로 이동하는 방식으로 진행해주시면 됩니다.

 

 

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
 
        int arr[] = new int[1000001];
 
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int g = Integer.parseInt(st.nextToken());       // 얼음의 양
            int x = Integer.parseInt(st.nextToken());       // 좌표
 
            arr[x] = g;
        }
 
        int window = 0;
        for (int i = 0; i < k + 1 && i < arr.length; i++) {
            window += arr[i];
        }
 
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            int low = i - k - 1;
            int high = i + k + 1;
 
            if (low > 0) {
                window -= arr[low];
            }
 
            if (high < arr.length) {
                window += arr[high];
            }
 
            if (max < window) {
                max = window;
            }
        }
 
        bw.write(max + "\n");
        bw.flush();
    }
 
}