[알고리즘] 최대 매출

Q. 현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 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

 

 

<나의 풀이>

public static 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;
}

 

 

 

 

 

<오늘 공부한 내용>

- 이 문제를 이중 for 문으로 구현할 경우 O(n^2) 의 시간복잡도가 걸린다.

- 슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용하다.

- 투 포인트 알고리즘과 비교해보면, 투 포인트 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하지만,

   슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점이 있다.