[Sliding window] 최대 매출 .java

설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.

만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면 12 15 11 20 25 10 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

 

 

내 풀이

이중 for문 -> 복잡도가 너무 큼 O(N^2) => n의 최대 100,000임

=> 3일만 보면 되기 때문에 슬라이딩 윈도우로 풀기 -> O(N)

 

1. 인덱스 0~2의 값을 더한 초기 윈도우의 값 구하기

2. 하나의 값씩 윈도우 이동

=> 인덱스 3 값 추가, 인덱스 0 값 빼기 => arr[i] - arr[i-k]

3. 이전의 최댓값과 현재 구한 값 중 최댓값 구하기

 

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
           arr[i] = sc.nextInt();
        }

        int sum  = 0;
        int answer = 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);
        }
        System.out.println(answer);


    }
}

 

 

다른 풀이

비슷한  코드지만 함수형이 다름~!

import java.util.Scanner;

public class Main {
    public int solution(int n , int k, int[] arr){
        int answer = 0;
        int 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);
        }

        return answer;

    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }


        System.out.println(T.solution(n,k,arr));


    }
}

💡💡

아직 슬라이딩 윈도우에 익숙하지 않아 하나씩 미는 법을 구현하기 어려워 애를 먹었다

총합의 의미를 다시 생각하니까 단순히 새로운 값 하나 더하고 젤 오래전에 있던 값을 빼면 그게 총합이라는 것을 이용하여 풀었다