연속부분수열의 합이 특정숫자 m이하가 되는 경우를 구하는문제
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr) {
let answer = 0;
let sum = 0;
let counter = 0;
let left = 0;
for (let i = 0; i < arr.length; i++) { //하나씩 검사한 반복문
if (arr[i] <= m) {
counter = counter + 1
}
}
for (let r = 0; r < arr.length; r++) {
sum = sum + arr[r]
if (sum <= m) {
counter = counter + 1
}
while (sum > m) { //참일경우에 거짓이 될때까지 무한루프
sum = sum - arr[left] //값을 올려줘야해서 변수 설정해줌
left = left + 1 //left는 왼쪽에 있는 값을 하나씩 뺴주면서 5이하로 만들어주는 것
if (sum <= m) {
counter = counter + 1
}
} answer = counter //answer는 for문이 종료되고 나서 결과 출력 시켜야함
}
return answer;
}
let a = [1, 3, 1, 2, 3];
console.log(solution(5, a));
</script>
</body>
</html>
문제를 차근차근 이해해보자. (어렵다)
[1, 3, 1, 2, 3] 이라는 배열이있고, m이하(여기서는 5)가 되는 경우를 구해서 카운터를 올려주면 된다.
값을 저장시킬 counter, sum 변수를 만들어주었다.
문제는 합이 5이하가 되는 연속부분수열을 구하는것이니
{1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3},{1, 3, 1}로 10이다.
그래서 for문을 하나만 사용해서 [1,3,1,2,3]배열을 하나씩 검사하고
5이하의 숫자일경우에만 카운터를 올릴 수 있으니,
arr[i]가 m(5)보다 같거나 크면 카운터를 1올려달라고 넣어준다.(여기까지가 하나씩 검사한 반복문 끝!)
이번에는 [1,3] [1,3,1] => 5이하, [1,3,1,2] 여기서부터는 5이상으로 넘어가기때문에
앞에의 숫자를 하나씩 빼주는 로직을 만들어준다.
그리고 뺀 숫자의 다음숫자(3)부터 다시 계산해보면 [3,1] => 5이하 [3,1,2] => 5이상으로 넘어가기때문에
다시 3을 빼고 다음숫자(1)부터 계산해주는 것이다.
while문을 사용해서 조건이 거짓이 될때까지 무한루프를 만들어준다.
그리고 sum에 sum = arr[left]를 넣어서 조건이 참일때 배열의 첫번째 왼쪽 숫자부터 접근시켜준다.
조건문을 돌때마다 left를 1씩 증가시켜주고
sum 보다 m이 크거나 같을때 카운터를 1씩 증가시켜준다. (합이 5이하일때 1씩증가)
결과값을 answer에 잘 담아주면 10이 잘 출력된다.
'알고리즘' 카테고리의 다른 글
| [알고리즘 문제] 5-6번 (0) | 2022.07.13 |
|---|---|
| [알고리즘 문제] 5-5번 (0) | 2022.07.12 |
| [알고리즘 문제] 5-3번 (0) | 2022.06.17 |
| [알고리즘 문제] 5-2번 (0) | 2022.06.17 |
| [알고리즘 문제] 5-1번 (0) | 2022.06.17 |