섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)] 3. 최대 매출

문제

• 현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
• 만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
• 12 1511 20 2510 20 19 13 15
• 연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
• 여러분이 현수를 도와주세요.

입력

• 첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
• 두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

출력

• 첫 줄에 최대 매출액을 출력합니다.

입출력 예제

---

그만 놀고 공부량좀 늘리자..!

 

풀이 방식을 정리해보자.

이번 문제는 슬라이딩 윈도우 문제라고 한다.

슬라이딩 윈도우란 고정 크기의 윈도우(마스크, 영역)을 이동하면서 윈도우 내 데이터를 이용하는 알고리즘이라고 한다.

(나중에 좀 더 자세히 알아보자)

 

1. N과 K를 각각 입력받고 arr[ ] 배열에 값을 입력받는다.

• N : 매출 기록 일수
• K : 연속된 매출 기록 일수
• arr[ ] : 매출 기록 내역

2. 메소드 구현으로 넘어가보자.

 

3. 결과값을 저장할 변수 result와 연속 K일 간의 매출액을 합산할 변수 sum을 선언하고 0으로 초기화한다.

 

4. 0부터 K 까지 도는 for문을 작성하고 sum에 arr[0~K] 까지를 더한 값을 넣는다. 

• K가 3이라고 가정하면, arr[0] + arr[1] + arr[2] 를 한 값을 sum에 넣는 것이다.
• 이 때, 이 3개의 배열을 하나의 윈도우라고 본다. 아래 이미지를 참고하자.

5. 이제 K부터 N까지 도는 for문을 작성하고, arr[i] - arr[i-K] 를 구하여 sum에 더해준다.

• 위에 이미지를 참고해서 매출 기록이 [ 12 15 11 20 25 10 20 19 13 15 ] 라고 가정해보자. 
• 0부터 K 까지 도는 for문을 통해 arr[0] + arr[1] + arr[2] 한 값인 38(12+15+11) 을 sum에 넣는다.
• 다음으로 K부터 N까지 도는 for문을 통해 arr[3] - arr[0] 한 값인 46(38+8) 이 되고, 이 값을 sum에 넣는다. 
• 이 때 46은 15+11+20으로, 기존에 arr[0] + arr[1] + arr[2] 에서 arr[1] + arr[2] + arr[3] 인 값이 된다.
• 즉 맨 처음과 마지막 인덱스를 통해 sum 값을 변경하는 것이다.

6. Math.max() 를 사용해서 최대값을 result에 넣는다.

• Math.max() : 입력받은 두 개의 인자 중 작은 값을 리턴한다.

수행 결과를 확인한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.