[코딩테스트] 최대 매출

 

문제

현수의 아빠는 제과점을 운영합니다.

현수 아빠는 현수에게 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이하의 음이 아닌 정수입니다.

 

출력

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

 

 

 

예시 입력

10 3
12 15 11 20 25 10 20 19 13 15

예시 출력

56

 

 

 

 

 

문제 풀이

 

[첫번째 풀이]

import java.util.*;

public class Main {
    public int solution(int k, int[] revenue) {
        int i = 0;
        int max = 0;

        while (i < revenue.length - k) {
            int sum = 0;
            for (int j=i; j<i+k; j++) sum += revenue[j];

            max = Math.max(max, sum);
            i++;
        }

        return max;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] revenue = new int[n];
        for (int i=0; i<n; i++) {
            revenue[i] = scanner.nextInt();
        }

        Main main = new Main();
        System.out.println(main.solution(k, revenue));
    }
}

(Time 1321ms / Memory 35MB) Time Limit Exceeded

 

[두번째 풀이]

import java.util.*;

public class Main {
    public int solution(int k, int[] revenue) {
        int sum = 0, max = 0;
      
        for (int i=0; i<revenue.length; i++) {
            sum += revenue[i];

            if (i >= k) sum -= revenue[i-k];

            max = Math.max(max, sum);
        }

        return max;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] revenue = new int[n];
        for (int i=0; i<n; i++) {
            revenue[i] = scanner.nextInt();
        }

        Main main = new Main();
        System.out.println(main.solution(k, revenue));
    }
}

(Time 790ms / Memory 35MB)

 

 

 

- 첫번째 풀이는 while 문을 돌면서 for 문을 돌아서 입력 받은 일수 동안의 수를 더하여 가장 큰 값을 추출해 냈는데 입력값이 커지면 시간 초과로 실패가 떨어지는 경우다.

- 두번째 풀이에서는 풀이 영상처럼 for문 한 번만에 해결할 수는 방식을 이용했다. for 문을 돌면서 더하기와 빼기를 이용하는 방법이다.