[알고리즘]최대 매출 - 배열에서 연속된 요소 N개의 최대 합 구하기

▷ 문제

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

현수 아빠는 현수에게 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

▷ 풀이

1. 다중 for문 사용

import java.util.Scanner;

public class Main {	
    public int solution(int n, int k, int[] arr){
        int answer = Integer.MIN_VALUE;

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

        return answer;
    } 

    public static void main(String[] args){
        Main main = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++){
          arr[i] = kb.nextInt();
        }

        System.out.println(main.solution(n, k, arr));
      }
  }

 

2. 포인터 사용

import java.util.Scanner;

public class Main {	
    public int solution(int n, int k, int[] arr){
      int answer, sum=0;

      //먼저 0번째 값부터 k-1의 값까지 k개의 값을 더해줍니다.
      for(int i=0; i<k; i++) {
        sum += arr[i];
      }
      answer = sum;
		  
      //연속된 값 중 첫번째 값은 빼고  k번째 값을 더하여 이를 answer와 비교해줍니다. 
      for(int i=k; i<n; i++){
			  sum += arr[i] - arr[i-k];
			  answer = Math.max(answer, sum);
		  }

		  return answer;
    } 

    public static void main(String[] args){
        Main main = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++){
          arr[i] = kb.nextInt();
        }

        System.out.println(main.solution(n, k, arr));
      }
  }

▷ 핵심 포인트

1. 포인터를 쓸 경우 시간을 단축시킬 수 있으므로 상황에 맞게 알맞는 방법을 택합니다.