인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

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

sksn12님의 프로필 이미지
sksn12

작성한 질문수

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

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

시간복잡도

작성

·

158

0

문제를 풀긴 했는데 시간복잡도가 좋은지 모르겠습니다 ㅜㅜ
시간복잡도와 반례가 있으면 알려주시면 감사하겠습니다

function solution(m, arr) {
  let answer = 0;
  let p1 = 0;
  let p2 = 1;
  while (p1 < arr.length) {
    if (arr[p1] === m) {
      p1 += 1;
      p2 += 1;
      answer += 1;
    } else {
      let sum = 0;
      for (let i = p2; i >= p1; i--) {
        sum += arr[i];
      }
      if (sum === m) {
        answer += 1;
        p1 += 1;
        p2 = p1 + 1;
      } else if (sum < m) {
        p2 += 1;
      } else {
        p1 += 1;
        p2 = p1 + 1;
      }
    }
  }
  return answer;
}

답변 1

0

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

안녕하세요^^

시간복잡도가 O(n)은 아닙니다. 영상의 방법을 익혀두셔야 합니다.

sksn12님의 프로필 이미지
sksn12

작성한 질문수

질문하기