[인프런] 03_03 최대 매출

📖  문제

---

• 첫 줄에 N과 K가 주어진다.
• 두 번째 줄에 N개의 숫자열이 주어진다.
  • N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하시오.

출력 예시

 

⚠️  주의사항

---

• for문을 다 돌려서 할 수도 있지만 슬라이딩 윈도우 방식으로 해결 해보겠습니다.

 

✍️  이해

---

슬라이딩 윈도우 방식이란

 

 

배열의 처음부터 순차적으로 탐색하고 부분 배열을 꺼내 보는 것입니다.

이때 부분 배열의 길이는 고정적(일정)합니다.

참고 블로그

 

 

아래와 같은 배열이 주어지고 10일 동안의 매출 중에 3일 동안의 최대 매출액은 얼마인지 구할려고 해보겠습니다.

 

0	1	2	3	4	5	6	7	8	9
12	15	11	20	25	10	20	19	13	15

 

* 슬라이딩 윈도우 방식으로 해결
* 1. N개 만큼의 숫자열 입력, K입력
* 2. N개 의 배열 중에 K일 동안의 최대 값을 구해야 하므로 0 ~ K 일 동안의 값을 하나 생성
*  2-1. temp[0] + temp[1] ~ temp[K-1] + temp[K] 합으로 이루어진 변수 sum -> answer 저장
*  2-2. sum 에서 맨 처음 값 temp[0]을 빼고 temp[K+1] 추가 후 Math.max(answer, sum) -> answer 저장
* 3. return answer

 

✏️  풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Java03_03 {

    public int solution(int N, int K, int[] temp) {

        int sum = 0, answer = 0;

        for (int i = 0; i < K; i++) {
            sum += temp[i]; // 윈도우 생성
        }
        answer = sum; // 최댓값을 구해야 하므로 우선 answer에 sum값 대입

        for (int i = K; i < N - K; i++) {
            sum += (temp[i] - temp[i - K]);
            // [] -> 윈도우 현재 sum 값
            // [10 7 8] 7 8 2 9 -> 10 [7 8 7] 8 2 9
            // 즉 맨 처음꺼는 빼고 마지막에서 + 1 된 값은 더해주면 된다.

            answer = Math.max(answer, sum); // answer 와 sum 중 큰 값이 -> answer 대입
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {

        Java03_03 T = new Java03_03();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] temp = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < N; i++) {
            temp[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(T.solution(N, K, temp));
    }
}

---