[Algorithm/Java] 알고리즘 자바 최대 매출 구하기 (코딩테스트, Sliding window, 효율성, 연속합의 최대값)

---

1. 문제 설명

• 설명
  현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 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이하의 음이 아닌 정수입니다.
• 출력
  첫 줄에 최대 매출액을 출력합니다.

 

 

2. 문제 코드 및 풀이 설명

import java.util.Scanner;

public class MaximumSales {
  public static void main(String[] args) {
    MaximumSales T = new MaximumSales();
    Scanner kb = new Scanner(System.in);
    int n = kb.nextInt();
    int m = kb.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = kb.nextInt();
    }
    System.out.println(T.solution(arr, n, m));
  }

  // 해결방법
  // 입력받은 수를 m개 만큼 잘라서 더해주고 큰값으로 리턴 값을 교체
  // 다음 차례로 넘어갈 때마다 앞의 값은 빼주고 뒤에 값을 더해주는 방법을 사용
  // 시간복잡도를 줄이기 위하여
  public int solution(int[] arr, int n, int m) {
    int answer = 0;
    int sum = 0;

    for (int i = 0; i < m; i++) { // 첫번째 합 구하기
      sum += arr[i];
    }
    answer = sum; // 첫번째 합 대입

    // 앞에 값은 빼주고 뒤에 값을 더해주며 비교
    for (int i = m; i < n; i++) { 
      sum = sum + arr[i] - arr[i - m];
      if (answer < sum) answer = sum;
    }

    return answer;
  }

  // 잘못된 방법 O(n^2)
  // 시간이 너무 오래걸림, 이중 반복문
  public int solution2(int[] arr, int n, int m) {
    int answer = 0;
    for (int i = m - 1; i < n; i++) {
      int sum = 0;
      for (int j = m - 1; j >= 0; j--) {
        sum += arr[i - j];
      }
      if (answer < sum) answer = sum;
    }

    return answer;
  }
}

 

3. 출력 예시

입력
10 4
12 15 60 30 20 54 16 56 32 44

출력
164

 

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의