[JAVA] 슬라이딩 윈도우를 이용한 최대 매출

 

문제 유형: 슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 창문이 옆으로 이동하는 것처럼 문제를 푸는 방식이다. 어떤 배열이나 리스트에서 연속되는 원소의 최대합을 구한다고 가정해보자. 만약 이중for문을 이용해서 풀게 된다면 데이터에 접근할 때 중복이 생기게된다. 예를 들면, {1, 2, 3, 4, 5, 6,}에서 4개의 연속되는 원소의 합을 구할 때 이중 for문을 이용하면 첫 번째: 1, 2, 3, 4를 접근하게 되고, 두 번째에서 2, 3, 4, 5에 접근하게 된다. 즉 2, 3, 4는 중복되서 값을 읽어야 하기 때문에 낭비가 발생하게된다. 

 

슬라이딩 윈도우 알고리즘을 이용하면 이러한 중복을 해결할 수 있다. 슬라이딩 윈도우는 일단 첫 4개의 값을 읽은 다음에 다음번 부터는 한 개의 for문을 이용해서 오른쪽 값을 추가하고 왼쪽의 값은 뺀다. 그렇게 때문에 가운데에 원소의 값은 중복이 일어나지 않게 된다. 

 

슬라이딩 윈도우 알고리즘은 투포인터 알고리즘과 자주 비교된다. 두 알고리즘의 차이점은 부분 배열의 길이가 고정적이냐 가변적이냐이 따라 다르다. 슬라이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적인 반면 투포인터 알고리즘은 고 부분 배열의 길이가 가변적이다.

 

 

코드

package 인프런.투포인터와슬라이딩윈도우.최대매출.방법1;

import java.util.Scanner;

public class Main {

    public int solution(int days, int sequence, int[] arr) {
       int max = Integer.MIN_VALUE; // 최댓값
       int sum = 0 ;    // 합을 담을 임시 변수
       for (int i=0; i<sequence; i++) { // 우선 초기값 설정
           sum += arr[i];
       }
       max = sum;   

       for (int i= sequence; i<days; i++) { 
           sum += (arr[i] - arr[i-sequence]);   // 윈도우를 오른쪽으로 옮기기
           max = Math.max(sum, max);    // 큰 값을 max에 넣어주기
       }

       return max;
    }
    
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int days = in.nextInt();
        int[] arr = new int[days];
        int sequence = in.nextInt();
        for (int i=0; i<days; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println(T.solution(days, sequence, arr));
    }
}

느낀점

성능이 중요하지 않은 상황에서 이중 for문을 사용해도 상관없다. 하지만 배열 원소가 많아지고 탐색해야될 횟수가 많아 질 수록 좋은 알고리즘의 효과는 상당하다.