슬라이딩 윈도우
앞서 포스팅한 투포인터 알고리즘이랑 슬라이딩 윈도우랑 같은점은 부분 수열을 활용한점입니다. 투포인터는 lt, rt 같이 배열의 인덱스 변수 2개를 만들어서 포인터로 활용했습니다. 부분 수열의 합이 x 랑 같은 갯수가 몇 개인가? x 보다 작거나 같은 부분 수열 갯수가 몇 개인가?의 문제 였습니다.
슬라이딩 윈도우랑 투포인터랑 차이점은 투포인터는 부분 수열의 크기가 가변적인데에 반해 슬라이딩 윈도우는 고정적이란 겁니다. 즉 3개다, 4개다 식으로 문제에서 n개라고 말해줍니다.
연속된 부분 수열 갯수 가변일땐 투포인터, 고정일땐 슬라이딩 윈도우를 사용하면 됩니다.
슬라이딩 윈도우는 말그대로 창문들이 슬라이딩한다, 루프를 돌때마다 옆으로 한칸씩 이동하는 상상을 하면 그 정의가 이해됩니다. 단 창문의 갯수는 고정적이라 3개라 하면 3개의 창문이 배열 처음부터 끝까지 그대로 루프를 돌면서 이동하는 형태입니다.
문제
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 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)과 M(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
- 출력
첫 줄에 최대 매출액을 출력합니다.
- 입력예제
10 3
12 15 11 20 25 10 20 19 13 15
- 출력예제
56
풀이 - 논리
투포인터로 lt랑 rt 이렇게 투포인터 만들어 풀어도 되는데, 슬라이딩 윈도우를 공부하는 겸 슬라이딩 알고리즘을 사용해 풀어 보겠습니다.
이 문제의 풀이법은 요약하자면
- 주어진 array에서 index 0부터 주어진 k일 까지 최초 sum을 구합니다.
for(let i=0; i<k; i++){ sum += array[i] }
- sum을 임시로 answer 변수에 할당하고, array[0]~[k]까지 합해진 sum값에서 for 루프 한번 돌때마다
sum = array[k+1] - array[부분 수열의 각 첫번째 index]를 할당해줍니다. 위 식의 의미는 만약 k=3이 주어졌다면 1번 작업에서 [0][1][2] 인덱스 요소가 sum에 합쳐졌을텐데, 그 sum값에서sum += +array[4] - array[0]를 계산해주게 됩니다. 그럼 배열로 상상하면 창문 3개가 오른쪽 한칸 옆으로(인덱스 0 값을 삭제하고 4의 값을 추가했으니) 슬라이딩 이동 한 것이 됩니다. 이 걸 for문 만들어서 for문 조건식 부분에 <array.length까지 돌아가도록 만들어 줍니다.- sum에 최대값을 비교해줍니다. if를 사용해서 answer에 할당해도 되고
answer = Math.max(answer, sum);을 사용해서 각 sum과 answer를 비교해 answer에 할당해줍니다.
풀이 - 코드로..구현하면
- 1번을 구현하면 아래와 같습니다.
2,3. 을 같이 구현하면 아래와 같습니다.
위 부분 코드가 멋진게, k 정도의 차이를 앞의 인덱스를 [i-k]로 하고 for문으로 i를 증감 시켜줘서 코드를 직관적이고 깔끔하게 만들었습니다.
또한 두번째Math.max(비교값1, 비교값2)를 사용해서 if 조건문 필요없이 max값 찾을수 있도록 깔끔하게 구현되었습니다.
