인프런 커뮤니티 질문&답변

wlsgml450님의 프로필 이미지
wlsgml450

작성한 질문수

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

3. 연속부분수열1(Two Pointers Algorithm)

코드 리뷰 부탁드립니당

작성

·

272

0

  function solution(m, arr){
    let answer = 0;
    for (let i = 0; i < arr.length; i++) {
        let sum = 0;
        let index = i;
        while(sum < m) {
            sum += arr[index];
            if (sum === m) {
                answer++;
                break;
            } else index++;
        }
    }
    return answer;
}

let a=[1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));

 

이렇게 작성해도 될까요 ?

 

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

네. 위와 같이 해도 답은 잘 나옵니다. 다만 시간복잡도가 영상의 방법보다 좋지 않습니다.

영상의 방법은 for문 안쪽의 while 문이 프로그램이 종료될때까지 총 n번 돌고 끝나는 시간복잡도 O(n) 방법입니다. 하지만 위에 코드는 while문이 매번 i부터 시작해서 a배열 전체를 탐색하는 구조입니다. 중간에 break가 있지만 그래도 위와 같은 코드는 시간복잡도를 O(n^2)로 간주합니다.

영상의 방법도 꼭 알아두시기 바랍니다.

wlsgml450님의 프로필 이미지
wlsgml450

작성한 질문수

질문하기