투 포인터 문제풀이를 하기 전에 알고리즘 개념 공부를 할 겸 동빈나님 영상을 보고 예제를 풀어봤다. 영상에 예제 설명이 자세하게 되어 있어 문제 설명은 생략하고 간단히 풀이만 기록해두려고 한다.
✏️ 투 포인터 (Two Pointers)
투 포인터 알고리즘 예제는 이중 for문을 사용하여 시간복잡도 O(N^2)로 한번 풀어보고 투 포인터 알고리즘을 적용하여 O(N)의 선형복잡도로 한번 풀어보았다.
1️⃣ 이중 for문 풀이
function solution(n, arr) {
let answer = 0;
for (let i = 0; i < arr.length; i++) {
let sum = 0;
for (let j = i; j < arr.length; j++) {
sum += arr[j];
if (sum > n) break;
else if (sum === 5) {
answer++;
sum = 0;
break;
}
}
}
return answer;
}
const arr = [1, 2, 3, 2, 5];
console.log(solution(5, arr));2️⃣ 투 포인터 풀이
function solution(n, arr) {
let answer = 0;
let sum = 0;
let end = 0;
// 시작점 start를 배열 시작부터 오른쪽으로 한 칸씩 옮김
for (let start = 0; start < arr.length; start++) {
// 끝점 end를 가능한 만큼 이동시킴
while (sum < n && end < arr.length) {
sum += arr[end];
// console.log('start: ' + start, 'end: ' + end, 'sum: ' + sum);
end++;
}
if (sum === n) answer++;
sum -= arr[start];
}
return answer;
}
const arr = [1, 2, 3, 2, 5];
console.log(solution(5, arr));위 풀이를 실행하면 아래와 같이 콘솔이 찍힌다.
answer++; 부분에도 console.log를 넣어보면 end 값이 답이 나오는 인덱스보다 하나 크게 찍히는데 while문 안의 sum += arr[end]가 실행되기 전에 answer 카운트를 올려주므로 사실상 의도대로 잘 작동하고 있다고 보아야 한다! 괜히 헷갈려서 한참 쳐다보고 있었다 🥲
이외에도 헷갈렸던 부분 몇 가지를 정리하자면
1. while은 코드 블럭을 실행하기 전 조건문을 평가
sum 값에 6이 찍히는 걸 보고 잠시 헷갈렸는데 start가 0, end가 1일 때의 sum이 3이기 때문에 while문이 실행되어 sum은 6이 되고 end는 2가 된다. 이후 조건문이 false이기 때문에 sum값에서 arr[start] 값을 빼준 후 start를 우측으로 한 칸 옮긴다.
start값이 1이 되면 sum === 5 이므로 while문의 코드 블록이 실행되지 않고 첫 번째 answer 콘솔이 찍힌다.
이중 for문 안에서 적절히 break를 사용해주면 for문 안에서 while을 사용한 것과 같은 게 아닌가 궁금증이 생겼다. 검색해보니 시간복잡도는 최악의 경우를 가정하고 계산하는 것이기 때문에 break 유무와 관계없이 이중 for문을 사용하게 될 경우 O(N^2)의 시간복잡도를 가지게 된다고 한다.
3. while의 시간복잡도
for문 안에 while을 쓰게 될 경우 이중 for문을 사용할 때랑 시간복잡도가 어떻게 다른 것인지 궁금했다.
위 글 두 개를 참고했는데 코드에 따라 달라질 것 같긴 하지만 for문에 while문을 중첩한 경우 이중for문을 사용한 경우인 O(N^2)보다는 작게 나오게 된다.
✏️ 구간 합 (Prefix Sum)
배열의 앞에서부터 특정 위치까지의 합인 접두사 합을 활용하는 방식
function solution(l, r, arr) {
let sum = 0;
const p = [0];
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
p.push(sum);
}
return p[r] - p[l - 1];
}
const arr = [10, 20, 30, 40, 50];
console.log(solution(2, 5, arr));구현도 간단간단!
prefix sum 을 나타내는 p 배열에 미리 0을 담아주었는데 L, R 등이 어떻게 주어지는지 문제에 따라 적절히 넣어주면 될 듯!
