Sliding window

코딩 테스트를 매일은 아니지만 LeetCode 에서 나름 그 주마다 몇개씩, 풀려고 했었다.

 

그런데 무언가 누간가의 도움이 필요 했으면 해서 최근에 inflearn의 자바 알고리즘 문제풀이를 이용해서 공부를 진행중이다.

 

이 강의를 이용하여 공부하던 중에 sliding window라는 말을 들었다.

 

코드를 미끄러지는 창문처럼 해결하도록 알고리즘을 구성한다는 것 같은데...

 

하여간 이곳에서 소개한 문제중 하나를 긁어왔다.

설명
현수의 아빠는 제과점을 운영합니다.
현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다.
이때 K=3이면 12 1511 20 2510 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
여러분이 현수를 도와주세요.

입력
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

출력  첫 줄에 최대 매출액을 출력합니다.

예시
10 3                                           =>                            56
12 15 11 20 25 10 20 19 13 15 

 

필자는 문제를 해결하기 위해 다음과 같이 생각했다. 

 

첫번째로 입력 받는 값은 총개수, 두번째로 입력 받는 값은 연속된 날 수이기 때문에

 

두번째로 입력받는 값만큼 반복문을 돌리려고 했다.

 

그러면 결국 이중 for문 사용은 피할 수 없긴 하다.

 

 

내 풀이

package twopointerandslidingwindow;

import java.util.Scanner;

public class MaximumEarning {

    public static void main(String[] args) {

        MaximumEarning me = new MaximumEarning();
        Scanner kb = new Scanner(System.in);
        int[] condition = new int[2];
        for(int i=0; i<2; i++){
            condition[i] = kb.nextInt();
        }

        int[] a = new int[condition[0]];
        for(int i=0; i<condition[0]; i++){
            a[i] = kb.nextInt();
        }

        me.solution(condition[0], condition[1], a);
    }

    //내 풀이
    //포인터 부분을 기억하는 것보다 굳이?? 라고햇지만... for문 두개면 좀 성능 떨어질수도?
    private void solution(int times, int sequence, int[] a) {
        int count=0;
        int result = Integer.MIN_VALUE;
        for(int i=0; i<a.length-sequence; i++){
            int p1 = i;
            int total = 0;
            for(int j=0; j<sequence; j++){
                total += a[p1++];
            }
            result = Integer.max(result, total);
        }
        System.out.println("result = " + result);
    }

}

흐름을 생각해보자

 

주어진 예시처럼 내가 계산할 총 날짜는 10일, 연속된 날짜는 3일이다.

10 3 입력 후

12 15 11 20 25 10 20 19 13 15 => a 배열에 담아주는를 입력했다.

 

처음 날짜가 왔을 때 그 입력한 연속된 날짜만큼을 덧셈하고 싶다.

 

그래서 a[0]에서부터 a[2]까지 덧셈을 해야 할 것이다. 

 

여기서 문제는 OutOfBoundaryException이 나오면 안되니 가장 밖에 있는 for문의 경우에는 입력한 갯수를 넘지 않게 총 입력 받은 날짜에 더해야 하는 연속적인 날을 뺴주었다.

 

그리고 두번째 for문에서는 시작점을 지정해준 포인터를 기준으로 계산해야 하는 연속된 날짜를 더하도록 했다.

 

a[0] ~ a[2] 를 더해서 현재 최대 값인지 비교하고, a[1] ~ a[3]를 더해서 현재 최대 값인지 비교하고.......a[7] ~ a[9] 를 더해서 현재 최대값인지 비교하였다.

 

그런데 이것보다 더 나은 방법을 소개해줬다.

 

silding window 알고리즘이 바로 그것인데

 

일정한 범위를 유지하면서 이것을 이동하는 방법을 말한다.

 

이 방법을 이용하면 굳이 불필요하게 for문을 한 번 더 사용할 필요가 없다.

 

강의 풀이

package twopointerandslidingwindow;

import java.util.Scanner;

public class MaximumEarning {

    public static void main(String[] args) {

        MaximumEarning me = new MaximumEarning();
        Scanner kb = new Scanner(System.in);
        int[] condition = new int[2];
        for(int i=0; i<2; i++){
            condition[i] = kb.nextInt();
        }

        int[] a = new int[condition[0]];
        for(int i=0; i<condition[0]; i++){
            a[i] = kb.nextInt();
        }

        me.solution1(condition[0], condition[1], a);
    }

    //강의 풀이
    public void solution1(int n, int k, int[] arr) {
        int answer = 0, sum = 0;
        for (int i = 0; i < k; i++) sum+=arr[i];
        answer = sum;
        for(int i=k; i<n; i++){
            sum+=(arr[i]-arr[i-k]);
            answer=Math.max(answer, sum);
        }
    }

}

 

12 15 11 20 25 10 20 19 13 15 를 비교하는데 기본적으로 더해야 할 연속된 일수는 2이상, n일 이하다.

 

그렇기에 맨 처음의 날짜는 더하기로 한다. 

 

그리고 그 다음에 반복문을 이용한다. 그리고 앞으로 새로이 더하는 날을 더하고, 뒤의 날짜는 제거하는 것이다.

 

다음의 흐름을 생각해보자.

 

12 15 11 20 25 10 20 19 13 15 중 연속된 3일 중 최대 값을 구하는 경우에는

 

12 15 11까지 더한다.

 

그다음 for문은 3부터 시작한다. 

 

answer = 12+ 15 + 11 로 값이 배정되어 있는데

 

for문을 다시 사용하지 않고 15 11 20을 더한다. 그리고 맨 처음 더한 값을 제외한다. 왜? 3일 연속의 범위에 벗어난 친구는 제거해야 비교가 가능하기 때문이다.

 

새롭게 더하게된 sum은 15 + 11 + 20이고 이것을 기존에 answer와 비교해서 최대값을 새로이 answer에 배정한다. 

 

 

---

for문을 두번 돌리는 순간 두배로 걸리던 작업이 한번의 순회로 처리가 된다. 

 

이점이 인상 적이어서 안지는 좀 됐지만 이 글을 적었다.

 

이래서 알고리즘에 대한 공부도 어느정도 해야 한다고 생각하는게, 번뜩이는 아이디어가 필요한 순간이 코딩 과정에서

나름 많은데, 이것을 어떻게 좋은 방식으로 refactoring을 고민하게된다.

 

여러 방법을 알고 있으면 그나마 빠른 방법을 찾는데 도움이 되지 않을까 생각한다.