알고리즘) N일간 연속된 K일 동안의 최대 매출액

 N일 동안의 매출 중 연속 K일 동안의 최대 매출액을 출력하는 문제다. 첫 줄에 N(5 <= N <= 100000)일과 K(2 <= k <= N)일이 입력되고, 다음 줄에 N일 간의 일일 매출액이 입력된다.

 

초기 작성 코드

import java.util.*;

public class Main {
    private int solution(int n, int k,  int[] arr) {
        int answer = 0;
        int idx1 = 0, idx2 = 0;
        while (idx1 < n - k) {
            idx2 = idx1;
            int sum = 0;
            while(idx2 < idx1 + k) {
                sum += arr[idx2++];
            }
            if (answer < sum) answer = sum;
            idx1++;
        }

        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        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(al.solution(n, k, arr));
    }
}

 

개선 코드

import java.util.*;

public class Main {
    private int solution(int n, int k,  int[] arr) {
        int answer = 0;
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];
        answer = sum;

        for (int i = k; i < n; i++) {
            sum = sum - arr[i - k] + arr[i];
            if (answer < sum) answer = sum;
        }

        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        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(al.solution(n, k, arr));
    }
}

 

 기존에 코드를 짰을 때는 인자가 많아짐에 따라 Time Limit이 발생하기도 했다. 해설을 찾아보다가 힌트를 얻는 순간 머리를 한 대 맞은 듯한 기분이 들었다...ㅎ 루프를 매 요소마다 K번 돌게 했던 코드가 양 끝단의 값을 더하고 뺌으로써 한번만 돌게 되어 시간효율도가 상당부분 향상되었다.

---

1차 제출 결과

요소가 많아지자 제한 시간인 1000m를 초과했다.

 

2차 제출 결과

다섯번째 테스트의 경우에는 N이100000, K가 12000이 입력된 경우이다. 이 때에도 1000ms를 초과하지 않는다.