[Inflearn] 자바 알고리즘 문제풀이 #03-03 3. 최대 매출

문제

설명

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

 

출력 

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

 

 

 

내 풀이

import java.util.Scanner;

public class Main3_3 {
    public int Solution(int[] a, int k) {
        int sum=0, answer=0;
        for (int i = 0; i < a.length-k; i++) {
            for (int j = i; j < i+k; j++) {
                sum += a[j];
            }
            if(sum > answer) answer=sum;
            sum=0;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main3_3 T = new Main3_3();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        System.out.println(T.Solution(a, k));
    }
}

요즘 자주 만나는 Time Limit ^^

for문 하나만 써서 어떻게든 풀어보려 했는데 실패해따.

 

 

 

선생님 풀이

import java.util.Scanner;

public class Main3_3 {
    public int Solution(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(sum, answer);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main3_3 T = new Main3_3();
        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));
    }
}

내 생각을 저렇게 간단하게 풀 수 있다니!! 오늘도 풀이에 감탄하며 하나 더 배워간다ㅎ_ㅎ

(Sliding window) 기법 -> 정해진 크기의 틀 안에 값들을 미끄러지면서 비교 !

 

첫 3칸(k칸)의 합의 값을 sum, answer에 담아두고

그 다음 3칸(초록색), 그 다음 3칸, ... 의 합의 값이 더 크다면 answer에 넣어주는 간단한 방법이다.

 

 

 

결과