섹션 3. 투 포인터 & 슬라이딩 윈도우 - 3. 최대 매출

📌 문제 설명

현수 아빠는 제과점을 운영 중이며, N일 동안의 매출 기록 중 연속된 K일간의 최대 매출액을 구하려 합니다.

예를 들어 N=10이고,  매출이 아래와 같을 때 K=3일 경우 가장 높은 3일간 매출은 11+20+25 = 56입니다.

12 15 11 20 25 10 20 19 13 15

---

📝 입력 & 출력

입력

• 첫 줄: 정수 N(5 ≤ N ≤ 100,000), K(2 ≤ K ≤ N)
• 두 번째 줄: N개의 매출 기록 (각 값은 0~500)

출력

• 첫 줄에 연속된 K일 동안의 최대 매출을 출력

---

🔸 예제 입력 & 출력

예제 입력 1

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

 

예제 출력 1

56

---

💡 해결 방법

• 슬라이딩 윈도우(Sliding Window) 기법을 사용합니다.
• 처음 K일의 합을 구한 뒤, 윈도우를 한 칸씩 오른쪽으로 이동시키며 이전 합에서 가장 왼쪽 값을 빼고, 새로운 값을 더하는 방식으로 최대값을 갱신합니다.

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.*;

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

		for(int i = k; i < n; i++) {
			sum += arr[i] - arr[i - k];
			result = Math.max(result, sum);
		}
		return result;
	}

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

---

📖 코드 설명

1️⃣ 초기 구간 합 계산

for(int i = 0; i < k; i++) sum += arr[i];

• 첫 번째 윈도우(K일간)의 총합을 먼저 계산

2️⃣ 슬라이딩 윈도우 적용

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

• sum에 새로 들어온 값을 더하고, 가장 왼쪽 값을 제거
• Math.max()로 최대값을 지속적으로 업데이트

---

⏳ 시간 복잡도 분석

• 초기 합 계산: O(K)
• 슬라이딩 과정: O(N - K)
• 전체 시간 복잡도: O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

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