최대 매출
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 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이하의 음이 아닌 정수입니다.
▣ 출력설명
첫 줄에 최대 매출액을 출력합니다.
▣ 입력예제 1
10 3
12 15 11 20 25 10 20 19 13 15
▣ 출력예제 1
56
k인자로 받는 연속된 매출기록의 최대합을 구하는 문제.
✏️작성코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(k, arr) {
let answer, sum = 0;
for (let i = 0; i < k; i++) {
sum = sum + arr[i]
answer = sum
}
for (let i = k; i < arr.length; i++) {
sum = sum + arr[i] - arr[i - k]
answer = Math.max(answer, sum)
}
return answer;
}
let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));
</script>
</body>
</html>1. 합을 넣을 sum변수를 생성해준다.
2. k번 연속된 매출의 합을 구해야하니 [12,15,11][15,11,20].......
이렇게 돌아줄 첫번째 반복문을 사용한다.
( k번째만큼만 반복문을 돌아줘야하기때문에 i=k로 설정했다.)
3. 12,15,11를 더한 값을 sum에 넣고 answer에 대입한다.
-- 여기까지가 [12,15,11] 의 합(38) 세팅 --
4. 반복문을 하나 더 만들어서 arr를 돌린다.
(i를 k까지(3)만 돌려야하니 i=k로 넣어준다.)
5. 두번째 반복문을 돌려줄건데, sum(38)에서 다음숫자인 20을 더하고 앞에오는 숫자인 12를 빼준다.
=> 이렇게 하면 [12+15+11], [15+11+20], [11+20+25]....
이렇게 순차적으로 더해주는것과 같은 결과를 얻을 수 있다.
38+20-12= 46이고15+11+20=46로 결과적으로 같은 값이 나오게 된다.
38+20-12은 sum + arr[i] - arr[i - k] 가 된다.
인자로 k를 받고 있고, 숫자 20을 기준으로 숫자 12까지의 거리는 11,15,12 3칸만큼 떨어져있기때문에
인자로 받고있는 k와 동일한 값이다. 그래서[i - k]를 넣어준다.
6. k일 동안의 최대 합을 구해야하기때문에 answer에 Math.max() 를 사용하여 최대값을 구해준다.
=> 기존에 저장되어있는 answer 값과 현재의 sum 중에 큰값을 비교해줘야하기때문에
Math.max(answer, sum) 둘다 넣어주었다.
최대값 56 출력!
'알고리즘' 카테고리의 다른 글
| [알고리즘 문제] 5-7번 (0) | 2022.07.14 |
|---|---|
| [알고리즘 문제] 5-6번 (0) | 2022.07.13 |
| [알고리즘 문제] 5-4번 (0) | 2022.06.21 |
| [알고리즘 문제] 5-3번 (0) | 2022.06.17 |
| [알고리즘 문제] 5-2번 (0) | 2022.06.17 |