[알고리즘] Sliding window

배열에서 특정 구간을 설정하고 구간별 데이터를 비교해야할때 사용하기 용이한 알고리즘

 

ex) 매출기록이 배열로 주어질때 변수 k일간의 최대매출기록을 구하라

// n일간 매출기록 
// k = k일간의 연속매출 
// arr = 매출 array
// k일간의 최대매출기록은? 
public static int solution(int n, int k, int[] arr) {
    int answer = 0; // 최대 매출기록으로 갱신될 변수
    int sum = 0;

    for(int i=0; i<k; i++) { // 일단 k번째 까지의 요소를 전부 더해준다. 
        sum += arr[i];
    }
    answer = sum; // 현시점까지의 최대매출기록

    for(int j=k; j<n; j++) { // 이제 한칸씩 증감하여 최대매출기록을 갱신해준다.
        sum += (arr[j] + arr[j-k]); // j-k == 3-3.. 4-3... 5-3... 한칸씩 당겨진다.
        answer = Math.max(answer, sum);
    }
    return answer;
}

기준이될 k까지의 배열의 수로 데이터를 초기화 하고 반복문 수행 시 인덱스 값을 더하고

뒤에서 마지막(j-k)번째의 데이터를 제외 시키면 구간 k수만큼의 최대매출기록을 알 수 있다.