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

shut up and squat님의 프로필 이미지
shut up and squat

작성한 질문수

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

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

풀이 질문드립니다.

작성

·

102

0

저는 이렇게 짰는데 혹시 문제가 될만한 사항이 있을까요??

function solution(arr, m) {
    let answer = 0;
    let p1 = 0;
    let p2 = 1;
    let sum = 0;

    while (p1 < arr.length) {
        sum += arr[p1++];
        if (sum >= m) {
            (sum === m) && answer++;
            sum = 0;
            p1 = p2++;
        }
    }

    return answer;
}

input = [5, 2, 3, 8, 9, 1, 4, 1, 1];
console.log(solution(input, 10));

답변 1

2

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

안녕하세요^^

위에 코드는 p1이 매번 p2지점부터  새로 시작하는 결국에는 시간복잡도가 O(n^2)인 이중for문과 다를게 없습니다.

이 영상의 핵심은 투포인터 알고리즘으로 시간복잡도를 O(n)으로 하는것입니다.

shut up and squat님의 프로필 이미지
shut up and squat

작성한 질문수

질문하기