투 포인터 테크닉

지은·2023년 5월 30일

Algorithm

목록 보기

28/33

1차원 배열 문제나 문자열 문제에서 많이 사용한다.
한 배열에서 부분 배열을 다루거나, 한 배열에서 각각 다른 위치에 있는 두 개의 원소의 값을 가지고 계산할 때 사용한다.
1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값을 구한다.
완전 탐색 O(n²) 솔루션을 선형 시간 O(n)으로 성능을 향상시킬 수 있다.
연속된 구간의 원소들을 처리하기를 원하거나, 정렬된 배열에서 무언가를 구할 때 투포인터를 고려해볼 수 있다.

문제 1

다음 배열에서 원소들의 합이 x인 연속 부분배열의 개수를 구하라.
입력값 : arr = [1, 3, 6, 5, 2, 7, 9], x = 9
출력값 : 3 <= {3, 6} {2, 7} {9}

완전 탐색 풀이 `O(n²)`

function countSubArrSumOfX(arr, x) {
  let count = 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) {
        count++;
        break;
      }
    }
  }
  
  return count;
}

투 포인터 풀이 `O(n)`

left 포인터와 right 포인터는 0에서부터 시작한다.
sum이라는 변수에 left ~ right 사이에 있는 숫자들의 합을 저장해줄 것이다.

sum이 x보다 작다면 right 포인터를 +1 해주고,
sum이 x보다 크다면 left 포인터를 +1 해주며 배열의 마지막까지 이동한다.
이때 left 포인터가 이동하면 sum에서 left만큼 빼주고,
right 포인터가 이동하면 sum에서 right만큼 더해주며 sum 값을 계산한다.

function countSubArrSumOfX(arr, x) {
  let count = 0;
  let sum = 0;
  let left = 0;  // left 포인터
  let right = 0; // right 포인터
  
  while (right <= arr.length) { // right 포인터가 배열의 길이까지
    if (sum === x) {    // sum이 x와 같다면,
      count++;
      sum -= arr[left]; // sum 리셋
      left++;           // left 이동
    } else if (sum < x) { // sum이 x보다 작다면,
      sum += arr[right];  // sum에 right 더하고,
      right++;            // right 이동
    } else if (sum > x) { // sum이 x보다 크다면,
      sum -= arr[left];   // sum에서 left를 빼고,
      left++;             // left 이동
    }
  }
  
  return count;
}

문제 2

다음 정렬된 배열에서 두 개의 원소의 합이 x와 같은지 확인하고, 같다면 각 원소의 index를 반환하라.
입력값 : arr = [2, 4, 5, 7, 11, 15], x = 15
출력값 : [1, 4] <= {4, 11}

완전 탐색 풀이

function twoSumSorted(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j < arr.length; j++) {
      if (arr[i] + arr[j] === x && i !== j) {
        return [i, j];
      }
    }
  }
  return [-1, -1];
}

투 포인터 풀이

left 포인터를 배열의 0번째 요소, right 포인터를 배열의 마지막 요소 위치시켜준다.
두 원소의 합 sum이 x보다 작다면 left 포인터를 +1 해준다.
두 원소의 합 sum이 x보다 크다면 right 포인터를 -1 해준다.

function twoSumSorted(arr, x) {
  let left = 0;
  let right = arr.length - 1;
  
  while(left < right) { // left 포인터와 right 포인터가 만나면 반복문을 종료한다.
    let sum = arr[left] + arr[right];
    if (sum === x) {
      return [left, right];
    } else if (sum < x) {
      left++;
    } else if (sum > x) {
      right--;
    }
  }
  return [-1, -1];
}

코딩테스트 필수 테크닉, 투 포인터 기법- 코딩문 codingmoon

투포인터를 공부해야겠다고 생각하게 된 프로그래머스 문제..!! ✊

문제 3

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

n은 10,000 이하의 자연수 입니다.

입출력 예

n	result
15	4

완전 탐색 풀이

function solution(n) {
    let count = 0;
    
    for (let i = 1; i <= n; i++) {
        let sum = 0;
        for(let j = i; j <= n; j++) { // 1부터 sum에 더한다.
            sum += j;
            if (sum === n) { // sum === n이 되면
                count++;     // count + 1
                break;       // 반복문 탈출
            } else if (sum > n) { // sum > n이 되면 
                break;            // 반복문 탈출
            }
        }
    }
    return count;
}

투 포인터 풀이

function solution(n) {
    let count = 0;
    let sum = 1;
    let left = 1;  // left는 1
    let right = 2; // right는 2에서 시작
  
    while (left <= n) {
        if (sum === n) { // sum === n이 되면
            count++;     // count + 1
            sum -= left; // sum에서 left 빼주고
            left++;      // left 포인터 이동
        } else  if (sum < n) { // sum이 n보다 작다면
            sum += right;      // sum에 right 더하고
            right++;           // right 포인터 이동 
        } else if (sum > n) {  // sum이 n보다 크다면
            sum -= left;       // sum에 left 더하고
            left++;            // left 포인터 이동
        }
    }
    return count;
}