[알고리즘] 슬라이딩 윈도우

1. 슬라이딩 윈도우(Sliding Window)

하나의 윈도우(특정 범위)를 만들어 그 윈도우를 움직이면서 우리가 원하는 값을 찾아내는 알고리즘으로
O(n^2)인 시간복잡도를 O(n)으로 줄일 수 있다.

 

21921번: 블로그

 

위의 문제를 풀어보면서 슬라이딩 윈도우에 대해 알아보자

---

문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

 

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

 

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

예제 입력 1

5 2 

1 4 2 5 1

---

슬라이딩 윈도우의 원리

먼저 슬라이딩 윈도우의 흐름은 아래의 그림과 같다

 

우리가 구하려는 범위의 윈도우를 만들고 한칸씩 밀어가면서 방문자수의 합을 확인한다.

 

• 한 칸씩 밀 때는 기존에 구했던 합에서 다음 값을 더하고 처음 요소의 값을 빼주면 된다.
  •  처음 요소의 인덱스 구하는 방법 : 현재 인덱스 - 윈도우 크기
  • 1번째 합 : 1 + 4 = 5
  • 2번째 합은 5 + 배열[i] - 배열[X - i] = 5 + 2 - 1 = 6
• 위의 그림만 간단하게 머리에 넣고 코드로 보는 것이 이해가 더 빠를 것 같다. 코드를 보자.

코드 작성 

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

// https://www.acmicpc.net/problem/21921
public class Main {
    private static int N; // 블로그 시작한 후부터 일수
    private static int X; // 방문자 수를 구할 기간
    private static int[] visitCountArr;
    private static int maxVisit = 0;
    private static int maxPeriodCnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        visitCountArr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            visitCountArr[i] = Integer.parseInt(st.nextToken());
        }

        solution();
    }

    private static void solution() {
        // 처음 합계를 먼저 계산한다.
        for (int i = 0; i < X; i++) {
            maxVisit += visitCountArr[i];
        }
        maxPeriodCnt++;

        int sum = maxVisit;
        for (int i = X; i < N; i++) {
            sum += visitCountArr[i] - visitCountArr[i - X];
            if (sum > maxVisit) {
                maxPeriodCnt = 1;
                maxVisit = sum;
            } else if (sum == maxVisit) {
                maxPeriodCnt++;
            }
        }

        if (maxVisit == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(maxVisit);
            System.out.println(maxPeriodCnt);
        }

    }
}