[알고리즘] 투 포인터 문제 풀어보기

오늘처음해요·2024년 8월 18일

Two Pointers

주로 배열이나 리스트 같은 선형 자료 구조에서 효율적으로 문제를 해결하기 위해 사용되는 기법
두 개의 포인터를 사용하여 특정한 조건을 만족하는 구간이나 값을 찾는 데 유용함.

양방향

배열의 양 끝에서 시작하여 가운데로 이동하면서 조건을 찾음
두 숫자의 합이 특정 값이 되는 쌍을 찾는 문제 등에서 자주 사용 됨.

슬라이딩 윈도우

한 포인터는 고정, 다른 포인터를 움직이며 구간을 확장하거나 축소하는 방식
연속된 부분 배열의 합이 특정 값을 넘지 않도록 하는 최대 길이를 구하는 문제 등에서 사용.

장점

O(N^2) 시간 복잡도를 O(N)으로 줄일 수 있음

[프로그래머스 Lv.3 49%] 보석 쇼핑

보석 쇼핑 풀어보기

function solution(gems) {
    const typeAmount = new Set(gems).size;
    let left = 0;
    let right = 0;
    let minLength = gems.length + 1;
    let answer = [1, gems.length];
    const gemCount = new Map();
    
    while(right < gems.length) {
        const rightGem = gems[right];
        gemCount.set(rightGem, (gemCount.get(rightGem) || 0) + 1);
        right +=1;
        while(gemCount.size === typeAmount) {
            if(right-left < minLength) {
                minLength = right-left;
                answer = [left+1,right];
            }
            const leftGem = gems[left];
            gemCount.set(leftGem, gemCount.get(leftGem) -1)
            if(gemCount.get(leftGem) === 0) gemCount.delete(leftGem);
            left+=1
        }
    }
    return answer
}

동작

슬라이딩 윈도우 방식으로 left를 고정하고, right만 움직인다.
요소를 Map에 저장한다.
연속된 배열이 조건을 충족하면 left를 움직여 최소 길이를 저장한다.
1-3을 반복한다.

[백준 골드3] 소수의 연속합

const [[n]] = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt', 'utf8')
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.split(' ').map(Number));

const getPrimeArr = (limit) => {
  const primeArr = Array(limit + 1).fill(true);
  primeArr[0] = primeArr[1] = false;
  for (let i = 2; i * i <= limit; i++) {
    if (primeArr[i]) {
      for (let j = i * i; j <= limit; j += i) {
        primeArr[j] = false;
      }
    }
  }
  return primeArr.map((isPrime, idx) => (isPrime ? idx : null)).filter((num) => num !== null);
};

const primeArr = getPrimeArr(n);
let left = 0;
let right = 0;
let count = 0;
let sum = 0;

while (right < primeArr.length) {
  sum += primeArr[right];
  while (sum >= n) {
    if (sum === n) {
      count += 1;
    }
    sum -= primeArr[left];
    left += 1;
  }
  right += 1;
}
console.log(count);