인프런 커뮤니티 질문&답변
시간복잡도
작성
·
176
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;
}
퀴즈
투 포인터 또는 슬라이딩 윈도우 기법이 중첩 반복문보다 효율적인 주된 이유는 무엇일까요?
더 적은 메모리를 사용해서일까요?
코드가 더 짧아져서일까요?
대부분의 경우 O(N) 시간 복잡도를 달성해서일까요?
입력 데이터 크기에 영향을 받지 않아서일까요?





