[슬라이딩 윈도우] 3. 최대 매출

3. 최대 매출

 

설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 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이하의 음이 아닌 정수입니다.

출력

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

예시 입력 1 

10 3
12 15 11 20 25 10 20 19 13 15

예시 출력 1

56

 

 

<<풀이>>

 

-나의 풀이-

 

시간 복잡도 : O(N^2) 

 

sliding window는 무슨 말일까 ㅋㅋ 일단 내가 떠오르는 방식대로 풀었다. 처음에는 O(N) 방식을 찾아서 진행하고 있었는데 중간에 막히고 다시 수정하는 과정에서 제곱이 되어 버렸다 ㅎㅎ..  그렇게 정답은 맞을지라도 시간 초과로 결과가 나왔다 ㅋㅋ

import java.util.*;

class Main {

    public int solution(int N, int K, int[] arr) {
        int[] answer = new int[N - K + 1];
        int index = 0;
        int num = 0;
        for(int i = 0; i < N - K + 1; i++) {
            num = 0;
           for(int j = i; j < i + K; j++) {
               num += arr[j];
           }
           answer[index++] = num;
        }
        int max = 0;
        for(int i = 0; i < N - K + 1; i++) {
            if(answer[i] > max) max = answer[i];
        }
        return max;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();

        int[] arr = new int[N];
        for(int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        System.out.print(T.solution(N, K, arr));
    }
}

 

 

-강사님 풀이-

 

import java.util.*;

class Main {

    public int solution(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 j = K; j < N; j++) {
          sum  = sum + arr[j] - arr[j - K];
          answer = Math.max(answer, sum);
       }
       return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();

        int[] arr = new int[N];
        for(int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        System.out.print(T.solution(N, K, arr));
    }
}

 

뚜둔 ~ ㅜㅜ ㅋㅋ 무릎을 탁 친다 ㅋㅋ

시간만 충분하면 나도 이렇게 생각할 수 있었을까? 아니면 너무 색안경을 끼고 있다보니 안 보였던 것일까?

방식은 생각해볼 수 있을 정도로 간단한 방식이다.

 

말 그대로 창문을 옮겨 가면서 구하는 알고리즘이다.

간단하게 말하면 처음에 창문 틀을 정해두고 그 값을 구한 뒤, 다음 값은 칸 뒤에 하나를 더해주고 앞에 하나를 빼주면서 창문을 옮기는 형태로 바꿔주는 것이다. 이것이 sliding window 방식이다.

 

 

하하 ㅋㅋ 이 방식은 이중 for문 형태로 가서 제곱 형태의 시간 복잡도가 나올 수도 있는 것을 O(N)으로 복잡도를 줄일 수 있는 방식이다.

 

오늘도 한 수 배웠다 ㅎㅎ