초보 개발자의 일기

연속 부분수열 1 본문

코딩테스트/JS 알고리즘 문제(JS)

연속 부분수열 1

판다꼬마 2023. 1. 11. 19:03
728x90

문제

 

입력

  • 첫째 줄에 N , M이 주어진다.
  • 수열의 원소값은 1000을 넘지 않는 자연수이다.

 

 

출력

첫째 줄에 경우의 수를 출력한다.

 

입력 예시

8 6
1 2 1 3 1 1 1 2

출력 예시

3

풀이 방법

for문을 한번만 돌리면서 왼쪽 변수인 lt, 오른쪽 변수인 rt를 설정하여,

rt를 증가시키면서 sum값과 n값을 비교한다

값을 경우 answer를 증가

sum이 n보다 클거나 같을 경우 제일 앞 숫자를 빼면서 값을 비교하며 부분 수열을 만든다.

내 코드

<html>
<head>
    <meta charset="UTF-8">
    <title>출력결과</title>
</head>
<body>
<script>
    const sol = (n,a) =>{
        console.log(n,a)
        let answer=0;
        let sum=0;
        let lt=0;
        for (let rt=0; rt<a.length; rt++){
            sum+=a[rt];

            if(sum===n){
                answer++;
            }
            while(sum>=n){
                sum-=a[lt++]
                if(sum===n){
                    answer++
                }
            }
        }

        return answer;

    }

    let a=[1, 2, 1, 3, 1, 1, 1, 2];
    console.log(sol(6, a));
</script>
</body>
</html>

Solution

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(m, arr){
                let answer=0, lt=0, sum=0;
                for(let rt=0; rt<arr.length; rt++){
                    sum+=arr[rt];
                    if(sum===m) answer++;
                    while(sum>=m){
                        sum-=arr[lt++];
                        if(sum===m) answer++;       
                    }
                }        
                return answer;
            }
            
            let a=[1, 2, 1, 3, 1, 1, 1, 2];
            console.log(solution(6, a));
        </script>
    </body>
</html>

느낌점

 

728x90
저작자표시 비영리 변경금지

'코딩테스트 > JS 알고리즘 문제(JS)' 카테고리의 다른 글

최대 매출  (1) 2023.01.14
연속 부분수열2  (0) 2023.01.13
두 배열 합치기  (0) 2023.01.10
K번째 큰 수  (0) 2023.01.09
멘토링  (0) 2023.01.08
'코딩테스트/JS 알고리즘 문제(JS)' Related Articles more