연속 부분수열 1
N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을
작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.
▣ 입력설명
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.
▣ 출력설명
첫째 줄에 경우의 수를 출력한다.
▣ 입력예제 1
8 6
1 2 1 3 1 1 1 2
▣ 출력예제 1
3
연속 부분 수열의 합이 m일때 몇 번일지 구하는 문제!
📌작성코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr) {
let answer = 0;
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum = 0;
for (let j = i; j < arr.length; j++) {
sum = sum + arr[j]
if (sum === m) {
answer = answer + 1
break;
}
if (sum > m) {
break
}
}
}
return answer;
}
let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));
</script>
</body>
</html>우선 for문을 두 개 사용해서 배열을 비교해준다.
두 개를 사용한 이유는
첫번째 for문은? [1,2,1,3,1,1,1,2] 를 돌리는 것.
두번째 for문은? [2,1,3,1,1,2]/ [1,3,1,1,1,2]/ [3,1,1,1,2]....순차적으로 돌릴려고..
더한 값을 저장할 sum 변수를 만들고
sum + arr[j]( [2,1,3,1,1,2] / [1,3,1,1,1,2] / [3,1,1,1,2].~~~~)
를 넣어서 모든 값을 더하고 저장한다.
두번째 반복문이 시작점이 j=i 인 이유는?
첫번째 반복문에서는 i=0부터 시작하고
두번째 반복문은 두번째 인덱스부터 시작해야하기때문에 j=i 로 넣어주어야하기때문.
조건문을 사용하여 sum(더한값) 과 m (문제에서는 숫자6)이 같을 경우.
answer = answer +1을 하여 카운터를 올려주고
break로 끝내버린다. (루프 밖으로만 빠져나옴)
더한 값이 7이상이면 우리원하는 조건이 충족하지않기때문에
sum(더한값) 이 m 보다 클 경우 라는 조건문을 또 넣어준다.
7이상일 경우엔 바로 break로 종료!
이때 지금까지 더했던 sum의 값을 초기화해줘야하는데 첫번째 반복문이
끝나고 초기화를 해준다.
'알고리즘' 카테고리의 다른 글
| [알고리즘 문제] 5-5번 (0) | 2022.07.12 |
|---|---|
| [알고리즘 문제] 5-4번 (0) | 2022.06.21 |
| [알고리즘 문제] 5-2번 (0) | 2022.06.17 |
| [알고리즘 문제] 5-1번 (0) | 2022.06.17 |
| [알고리즘 문제] 4-5번 (0) | 2022.06.16 |