[알고리즘] Two pointers, Sliding window(3) : 최대 매출(JAVA)

👔 문제

Sliding window이다.

👖 풀이

위 문제를 2중 for문으로 풀게 되면 시간 복잡도가 복잡해 진다.(N * K)

Sliding window 방법

위와 같은 방법으로 한 칸씩 밀어가면서 나타내는 방법이다.
밀면서 각 원소의 합을 sum에 저장한다.

위의 설명을 소스코드로 옮겨보자!

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);
}
return answer;
}

🧦 소스코드

package algolecture;

import java.util.Scanner;

public class Main27 {

    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 i=k;i<n;i++){
            sum += (arr[i]-arr[i-k]);
            answer = Math.max(answer, sum);
        }
        return answer;
    }


    public static void main(String[] args) {
        Main27 T = new Main27();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = kb.nextInt();
        }
        System.out.print(T.solution(n,k,arr));
    }
}