[JS] 투포인터 (Two Pointer)

❗️투포인터 (Two Pointer)

• 2개 이상의 포인터를 두고 값을 비교하여 해결하는 알고리즘
• for문은 $O(N^2)$, 투포인터는 $O(N)$의 시간복잡도
• 하지만 모든 투 포인터가 $O(N)$의 시간복잡도를 가지는건 아님

✅ 풀이 방법

1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리킴
2. if (현재의 부분합 === target) count++;
3. else if (현재의 부분합 < target) end+=1;
4. else if (현재의 부분합 > target) start+=1;
5. 모든 경우를 확인할때까지 2~4 반복

⭐️ 포인터는 같은 지점에서 출발할 수 있고 양끝에서 출발할수있음

✅ 두 용액 - 백준 2470번
https://www.acmicpc.net/problem/2470

⭐️ 포인트를 다른 지점에서 출발하여 시작하는 경우

let dir = __dirname + "/2470.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let N = +input.shift();
let arr = input.shift().split(" ").map(Number);

arr = arr.sort((a, b) => a - b);

let start = 0;
let end = arr.length - 1;

let answer = [];
let min = Number.MAX_SAFE_INTEGER;
while (start < end) {
  let tmp = arr[start] + arr[end];
  if (Math.abs(min - 0) > Math.abs(tmp - 0)) {
    min = tmp;
    answer.push([arr[start], arr[end]]);
  }
  if (tmp >= 0) {
    end -= 1;
  } else {
    start += 1;
  }
}
console.log(answer[answer.length - 1].join(" "));

✅ 부분합 - 백준 1806번
https://www.acmicpc.net/problem/1806

⭐️ 포인트를 같은 지점에서 출발하여 시작하는 경우

let dir = __dirname + "/1806.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let [N, S] = input.shift().split(" ").map(Number);
let arr = input.shift().split(" ").map(Number);

let cumSum = [0];
for (let i = 1; i <= arr.length; i++) {
  cumSum[i] = cumSum[i - 1] + arr[i - 1];
}
let start = 0;
let end = 0;
let answer = Number.MAX_SAFE_INTEGER;
while (end < arr.length) {
  let cal = cumSum[end + 1] - cumSum[start];
  if (cal >= S) {
    answer = Math.min(answer, end - start + 1);
  }
  if (cal >= S) {
    start += 1;
  } else {
    end += 1;
  }
}
if (answer === Number.MAX_SAFE_INTEGER) {
  console.log(0);
} else {
  console.log(answer);
}