코딩테스트/JS 알고리즘 문제(JS)
최대 매출
판다꼬마
2023. 1. 14. 14:17
728x90
문제
입력
- 첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다. 두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
출력
첫 줄에 최대 매출액을 출력합니다.
입력 예시
10 3
12 15 11 20 25 10 20 19 13 15출력 예시
56풀이 방법
처음 내 풀이법은 솔루션과는 다르게 이중 for문을 돌면서 k의 값까지만 더하고 그 합들을 계속 비교해나가며
답을 구하는 코드였다.
이렇게 코드를 작성하면 시간복잡도가 O(n^2)이므로 좋은 코드가 아니였다.
솔루션의 코드는 처음 배열값에서 k번째 값까지의 합을 구한 후,
전에 구한 합에서 k+1의 값을 더하고 a[lt]의 제일 처음값을 뺌 으로서 새로운 합을 구했다.
이렇게 코드를 작성하면 시간복잡도가 줄어들어 더 좋은 코드가 된다.
내 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
const sol=(n,a)=>{
let answer=0;
let sum=0;
for (let lt=0; lt<n; lt++){
sum+=a[lt];
answer=sum;
}
for(let lt=n; lt<a.length; lt++){
sum+=(a[lt]-a[lt=n]);
answer=Math.max(sum,answer);
}
return answer;
}
let a=[12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(sol(3, a));
</script>
</body>
</html>Solution
<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+=arr[i];
answer=sum;
for(let i=k; i<arr.length; i++){
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>느낌점
시간복잡도를 잘 생각하여 코드를 작성하는 연습을 해야겠다.
728x90