자바스크립트로 보는 투 포인터

Doozuu·7일 전
슬라이딩 윈도우자바스크립트투 포인터

알고리즘&자료구조 (JS)

목록 보기
30/34

투 포인터는 어떤 알고리즘인가?

투 포인터는 배열에서 2개의 포인터를 조건에 따라 이동시키며 원하는 값을 찾는 알고리즘이다.
보통 left, right으로 불리는 두 가지의 포인터를 가진다.
매번 하나씩 포인터를 이동시키기 때문에 배열을 1번 순회하는 것과 같으므로 시간 복잡도는 O(N)이다.


투 포인터는 언제 쓰이는가?

  • 조건에 따라 두 개의 원소를 고르는 문제
  • 연속 구간 문제 (슬라이딩 윈도우) - 연속된 부분, 구간 합, 최소/최대 길이

투 포인터와 슬라이딩 윈도우의 관계

  • 투 포인터는 두 개의 포인터를 조건에 따라 자유롭게 이동한다. (구간 크기가 자유로움)
  • 슬라이딩 윈도우는 두 개의 포인터로 고정된 구간을 유지하면서 이동한다.

투 포인터는 어떻게 구현할 수 있는가?

예시 문제 ) 합이 target이 되는 연속 부분 수열의 개수 구하기

배열의 요소를 모두 순회할 때까지 아래 단계를 반복한다.

  • 합이 target보다 작으면 right 증가시키며 합산하기
  • 합이 target과 같아지면 count 증가시키기
  • 합이 target과 같거나 크면 다음 탐색을 위해 left 증가시키기

문제마다 푸는 방식은 조금씩 다르지만 기본적으로는 아래처럼 두 개의 포인터를 조건에 따라 이동시키며 조건을 만족시키는 개수를 구하게 된다.

const arr = [1,2,3,4,5];
let target = 5;
let count = 0;
let right = 0;
let sum = 0;

for(let left=0;left<arr.length;left++){
  while(sum < target && right < arr.length){
    sum += arr[right]
    right++
  }
  if(sum === target) count++;
  sum -= arr[left]
}

console.log(count);

관련 문제 풀어보기

[백준] 두 용액

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0]
const liquids = input[1].split(' ').map(Number).sort((a,b) => a-b);
let answer = [];

function twoPointer(arr){
  let left = 0;
  let right = arr.length - 1;

  while(left < right){
    let sum = arr[left] + arr[right];

    if(answer.length === 0 || Math.abs(sum) < Math.abs(answer[2])){
      answer = [arr[left], arr[right], sum];
    }

    if(sum === 0){
      break;
    }else if(sum < 0){
      left++ 
    }else if(sum > 0){
      right-- 
    }
  }

  console.log(answer[0], answer[1])
}

twoPointer(liquids);

[백준] 부분 합

  1. 두 개의 인덱스를 모두 0으로 두고 시작한다.
  2. 합이 S와 같거나 클 때까지 right을 증가시킨다.
  3. 끝까지 더했는데도 S보다 작으면 불가능한 것이므로 중단한다.
  4. 합이 같거나 크면 최소 길이 업데이트하고 left를 증가시킨다.
  5. 모든 배열 탐색해서 최소 길이 출력하고 불가능하면 0 출력한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N,S] = input[0].split(' ').map(Number);
const arr = input[1].split(' ').map(Number);
let answer = Infinity;
let right = 0;
let sum = 0;

for(let left=0;left<N;left++){
  while(sum < S && right < N){
    sum += arr[right];
    right++;
  }

  if(sum < S) break;

  answer = Math.min(answer, right-left);
  sum -= arr[left];
}

console.log(answer === Infinity ? 0 : answer);

[백준] 소수의 연속합

문제 이해

  • 연속된 소수의 합으로 나타낼 수 있는 경우의 수
  • 2부터 시작해서 타겟보다 작으면 다음 소수 더하기
  • 타겟과 같으면 카운트 증가
  • 타겟보다 크면 이전 값 제거

N까지의 소수를 효율적으로 구해두는 것이 중요하다.
이때 소수를 효율적으로 구하기 위해 에라토스테네스의 체 알고리즘을 이용해야 한다.(일일이 소수 판별하면 시간 초과)
에라토스테네스의 체 알고리즘은 모든 수가 소수의 곱으로 이루어져 있다는 성질을 활용해 2의 배수, 3의 배수, 5의 배수,, 를 모두 제거하여 소수만 남기는 알고리즘이다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
let answer = 0;
let right = 0;
let sum = 0;

function getPrimes(n) {
  const isPrime = Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }

  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }

  return primes;
}

const primes = getPrimes(N);
  
for(let left=0;left<primes.length;left++){
  while(sum < N && right < primes.length){
    sum += primes[right];
    right++;
  }

  if(sum < N) break;

  if(sum === N) answer++
  sum -= primes[left]
}

console.log(answer);

[백준] 고냥이

문제 설계

  • 배열을 순회하며 종류가 N보다 작거나 종류가 N이지만 다음 종류가 이미 있으면 계속 right 증가시킨다.
  • 이때 새로운 종류면 객체에 추가하고 있던 종류면 카운트를 증가한다.
  • 문자열 최대 길이를 업데이트한다.
  • 문자열 개수가 1개면 객체에서 제거하고, 개수가 2개 이상이면 카운트를 1 감소시킨다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
const str = input[1];
const type = {};
let answer = 0;
let right = 0;
  
for(let left=0;left<str.length;left++){
  while((Object.keys(type).length < N  || Object.keys(type).length === N && type[str[right]]) && right < str.length){
    type[str[right]] = (type[str[right]] || 0) + 1;
    right++;
  }

  let len = right - left;

  if(len > answer) answer = len;

  if(type[str[left]] === 1){
    delete type[str[left]];
  }else{
    type[str[left]]--;
  }
}

console.log(answer);

위의 풀이는 while문에서 매번 객체를 배열로 변환해야 하므로 시간 복잡도면에서 비효율적이다.
더 효율적으로 풀기 위해 알파벳 종류와 카운트를 각각 저장해둘 수 있다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
const str = input[1];

const count = Array(26).fill(0); // 알파벳 소문자 전체 개수
let kind = 0;
let answer = 0;
let right = 0;
  
for(let left=0;left<str.length;left++){
  while (right < str.length) {
    const rIdx = str.charCodeAt(right) - 97; // 알파벳 위치

    if (count[rIdx] === 0 && kind === N) break; // 새로운 알파벳인데 이미 종류가 N개면 break

    if (count[rIdx] === 0) kind++; 
    count[rIdx]++;
    right++;
  }

  answer = Math.max(answer, right - left);

  const lIdx = str.charCodeAt(left) - 97;
  count[lIdx]--;
  if (count[lIdx] === 0) kind--;
}

console.log(answer);

[백준] 내려가기

슬라이딩 윈도우 + DP 문제
자바스크립트로는 메모리 초과 때문에 통과가 안 된다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
let maxDP = [0,0,0];
let minDP = [0,0,0];

const first = input[1].split(' ').map(Number)
maxDP = [...first];
minDP = [...first];

for(let i=2;i<=N;i++){
  const [a,b,c] = input[i].split(' ').map(Number);
  const prevMax = [...maxDP];
  const prevMin = [...minDP];

  maxDP[0] = a + Math.max(prevMax[0], prevMax[1])
  maxDP[1] = b + Math.max(prevMax[0], prevMax[1], prevMax[2])
  maxDP[2] = c + Math.max(prevMax[1], prevMax[2])

  minDP[0] = a + Math.min(prevMin[0], prevMin[1])
  minDP[1] = b + Math.min(prevMin[0], prevMin[1], prevMin[2])
  minDP[2] = c + Math.min(prevMin[1], prevMin[2])
}

console.log(Math.max(...maxDP), Math.min(...minDP));

[백준] 수열

K의 고정된 크기로 이동하며 최대 합 구하기
슬라이딩 윈도우 + 투 포인터
1. 초기 K개의 합 구해두기
2. right++, left++하며 최대 합 갱신하기

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N,K] = input[0].split(' ').map(Number);
const temperatures = input[1].split(' ').map(Number);
let answer = temperatures.slice(0,K).reduce((acc,cur) => acc+cur,0);
let right = K;
let sum = answer;

for(let i=0;i<N-K;i++){
  sum += temperatures[right] - temperatures[i];
  if(sum > answer) answer = sum
  right++
}

console.log(answer)
profile
Doozuu
모든게 새롭고 재밌는 프론트엔드 새싹
이전 포스트

자바스크립트로 보는 이분 탐색

다음 포스트

자바스크립트로 보는 DFS

0개의 댓글