🤘 투 포인터

🤘 투 포인터

• 문자열이나 1차원 배열(리스트)에서 사용되는 알고리즘
• 각각 다른 원소를 가르키는 두 개의 포인터를 사용해 배열이나 문자열을 순회하여 목표값을 찾는다.
• 부분 배열의 합(구간합)이나, 다른 위치에 있는 원소값을 이용한 값을 구할때 사용한다.
• 완전탐색인 O(n2) 솔루션을 O(n)으로 개선시킨다.

🤘 구간 합 문제

투포인터의 대표 문제인 구간 합 문제를 풀어보자!

다음 배열에서 원소들의 합이 x인 부분 배열의 개수를 구하여라
arr = [ 1, 3, 6, 5, 2, 7, 9 ], x = 9
답 : 3개 {3,6}, {2,7}, {9}

• 완전탐색 풀이 : 시간복잡도 O(n2)

  const solution = (arr, x) => {
    let cnt = 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 > x) {
          break;
        } else if (sum == x) {
          cnt++;
          break;
        }
      }
    }
    return cnt;
  }

  위 코드의 경우 depth가 2인 반복문이 사용되므로 시간복잡도는 O(n2)가 된다. 이를 개선하기 위해 투 포인터를 적용한다.
  
• 투포인터 풀이 : 시간복잡도 O(n)

  const solution = (arr, x) => {
    let cnt= 0;
    let sum = 0;
    let left = 0;
    let right = 0;
    while(right <= arr.length){
      if(sum === x){
        cnt += 1
        sum -= arr[left]
        left += 1
      }else if(sum < x){
        sum += arr[right]
        right += 1
      }else if(sum > x){
        sum -= arr[left]
        left += 1
      }
    }
    return cnt;
  }

  위 코드의 경우 left와 right라는 두 개의 포인트를 설정해둔다. 구간 합이기 때문에 두 값의 시작점은 0부터 시작한다.
  • right 값이 arr의 끝에 도달할 때까지 두개의 포인터 값을 조정하며 알고리즘을 수행한다.
  • 만약 목표값인 x와 sum이 동일하다면 구간합의 개수 cnt를 1 증가시켜 주고, 또다른 구간합을 찾기 위해 left값을 1 증가시켜준다. left값을 1 증가시켰으니 sum에서도 arr[left]의 값을 제거한다.
  • 만약 목표값인 x보다 sum이 작다면 right 값을 1증가시키고 구간합에 arr[right]값을 포함한다.
  • 만약 목표값인 x보다 sum이 크다면 left 값을 1 감소시키고 구간합에 arr[left]값을 제거한다.
  arr.length만큼 반복하기 때문에 시간 복잡도는 O(n)

투 포인터는 투 포인터는 정렬 수행 여부와 음수 양수 등을 고려하여 상황에 맞게 조건을 세우는 것이 중요하다.

🤘 투포인터 문제 추천

• 백준 두 수의 합
• 백준 두 용액
• 백준 부분합
• 백준 소수의 연속합
• 백준 냅색문제
• 백준 수 고르기
• 백준 수들의 합 2
• 백준 가장 긴 짝수 연속한 부분 수열 (large)
• 백준 회전 초밥
• 백준 겹치는 건 싫어
• 백준 대표 선수
• 백준 구간 자르기
• 백준 같이 눈사람 만들래?

🤘 Ref

• https://www.youtube.com/watch?v=SrMk-EdWRUE