자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 최대 매출

 

https://hyejin.tistory.com/1221

자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 공통 원소

-> 이전 문제 풀이 

 

 

 

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

 

 

문제 풀이 1

public int solution2(int n, int k, int[] a) {
    int max = Integer.MIN_VALUE;

    for (int i = 0; i <= n - k; i++) {
        int sum = 0;
        for (int j = 0; j < k; j++) {
            sum += a[i + j];
        }
        max = Math.max(max, sum);
    }

    return max;
}

👩🏻‍💻 : 나의 첫번째 시도였다... 이중 for문.. 그거 어떻게 안쓰는 건데... 

이중 for 문으로만 해결하려고 하니까... 자꾸 시간 초과 뜬다.. (당연함) 

 

 

 

문제 풀이 2

public int solution(int n, int k, int[] a) {
    int max = 0;
    int sum = 0;
    for (int i = 0; i <= n - k; i++) {
        if (i == 0) {
            for (int j = 0; j < k; j++) {
                sum += a[i + j];
                max = sum;
            }
        }else {
            sum = sum - a[i - 1] + a[i + k - 1];
            max = Math.max(max, sum);
        }

    }
    return max;
}

👩🏻‍💻 : 어떻게 풀어야할지.. 막막해하던 와중에... 강의 힌트로 Sliding Window 알고리즘을 사용한다 해서... 그럼 Sliding Window 가 뭔데! 하고 구글에 쳐서 해답을 알아냈다..! 유레카 ! 

보면 주어진 수 k 라는 창문을 만들고,, 그 다음 하나씩 옆으로 옮겨가면서 더하기를 하니까 기존 2개의 값은 그대로다. 이전 값은 빼고, 그 다음 값은 더하고... 하는 것일 뿐이기 때문에 

먼저 초반 i[0] + i[1] + i[2] 의 합은 구해줘야 하기 때문에 i= 0 일때는 k 만큼 sum에 누적해서 더하고, max 값에 sum 값을 넣어줬다. 

그 다음 부터는 sum에 맨 처음 값은 빼고, 이제 옆으로 한칸 옮기니 새로운 값을 더해주면 된다. 그 후 max와 sum 값을 비교해서 max 값을 갱신해주면 된다. 

 

 

 

문제 풀이 3

public int solution3(int n, int k, int[] arr) {
    int answer, 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문을 나눠서 먼저 sum에 배열의 맨 처음부터 k 번째까지의 값을 더해주고, 그 다음 for문에서는 k 번째부터 시작해서 arr[i] 값은 더하고, arr[i-k] 값은 빼주도록 했다.