투 포인터 알고리즘 - 개념정리

투포인터 알고리즘

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 목표값을 구하는 테크닉이다.

흔히 2,3,4,5,6,7번 학생을 지목해야 할 때 간단하게 2번부터 7번까지의 학생이라고 부르는 것과 같은 개념이다.

완전탐색으로 구현할 경우 O(n^2)의 시간복잡도를 투포인터를 사용하면 O(n)으로 성능 향상이 가능하다.

 

1️⃣ 두 배열 합치기

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요.

 

▣ 입력설명

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.

세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.

네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

 

▣ 출력설명

오름차순으로 정렬된 배열을 출력합니다.

 

▣ 입력예제 1

3

1 3 5

5

2 3 6 7 9

 

▣ 출력예제 1

1 2 3 3 5 6 7 9

---

구현 과정

오름차순으로 두 배열 모두 정렬되어있다는 가정하에 투포인터 알고리즘을 사용할 수 있다.

1

3

5

2

3

6

7

9

 

 

두 개의 포인터가 각 배열의 첫번째 요소를 가리킨다.

두 요소를 비교해서 작은 값을 결과 배열에 넣어주고, 작은 값을 가리키는 포인터를 오른쪽으로 한 칸 옮긴다.

같은 경우에는 두 요소 중 아무거나 결과 배열에 넣어준다.

 

1

3

5

2

3

6

7

9

1

2

3

3

5

 

위의 과정을 반복하면 오름차순으로 모두 정렬이 완료된 배열이 있을 것이다.

이렇게되면 남은 배열의 모든 요소를 차례대로 결과 배열에 넣어준다.

남은 배열의 요소는 정렬이 완료된 배열의 요소들보다 무조건 크기 때문이다.

 

1

3

5

2

3

6

7

9

1

2

3

3

5

6

7

8

---

구현 코드

function solution(a, b) {
  const result = [];
  let p1 = 0;
  let p2 = 0;
  const n = a.length;
  const m = b.length;

  while (p1 < n && p2 < m) {
    if (a[p1] <= b[p2]) {
      result.push(a[p1]);
      p1 += 1;
    } else {
      result.push(b[p2]);
      p2 += 1;
    }
  }
  while (p1 < n) {
    result.push(a[p1]);
    p1++;
  }
  while (p2 < m) {
    result.push(b[p2]);
    p2++;
  }

  return result.join(' ');
}

 

sort 함수를 사용하면 O(Nlogn)의 시간복잡도를 갖지만 투포인터를 사용하게 되면 O(n+m)의 시간복잡도를 갖는다.

---

 

2️⃣ 공통원소 구하기

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로 그램을 작성하세요.

 

▣ 입력설명

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.

두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.

네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

각 집합의 원소는 1,000,000,000이하의 자연수입니다.

 

▣ 출력설명

두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

 

▣ 입력예제 1

5

1 3 9 5 2

5

3 2 5 7 8

 

▣ 출력예제 1

2 3 5

---

이 문제도 배열이 오름차순으로 정렬되어있다는 가정에 투포인터 알고리즘을 적용할 수 있다.

먼저 예제의 배열을 오름차순으로 정렬하자.

 

1

2

3

5

9

2

3

5

7

8

 

이제 포인터가 가리키는 값을 비교하면서 공통 원소를 찾아주면된다.

주황색이 가리키는 값보다 하늘색이 가리키는 값이 크면, 배열이 오름차순으로 정렬되어있기 때문에 주황색은 현재 자신이 가리키는 값보다 더 큰 값에서 하늘색이 가리키는 값과 같은지 확인해야한다.

때문에 이 경우에는 주황색이 가리키는 값을 한 칸 옆으로 옮겨준다.

 

 

 

1

2

3

5

9

2

3

5

7

8

 

같은 값을 찾았다.

결과 배열에 2를 넣어준다. 그리고 포인터를 어떻게 옮길 지 생각해보자.

이제는 두 포인터가 가리키는 값보다 더 큰 수의 범위에서 공통 원소를 찾아야한다. 그렇기 때문에 두 포인터 모두 옮겨준다.

 

 

 

1

2

3

5

9

2

3

5

7

8

 

위의 과정을 반복하면 5까지 공통원소를 다 찾고 두번째 배열의 포인터는 계속 오른쪽을 가다가 더 이상 가리키는 값이 사라진다. 이렇게되면 더 이상 두 배열 사이에 공통 원소가 존재하지 않는 것이므로 순회를 종료하면 된다.

 

---

구현 코드

function solution(arr1, arr2) {
  const result = [];
  let p1 = 0;
  let p2 = 0;
  const n = arr1.length;
  const m = arr2.length;

  arr1.sort((a, b) => a - b); // O(Nlogn)
  arr2.sort((a, b) => a - b);

  while (p1 < n && p2 < m) {
    if (arr1[p1] > arr2[p2]) {
      p2++;
    } else if (arr1[p1] < arr2[p2]) {
      p1++;
    } else {
      result.push(arr1[p1]);
      p1++;
      p2++;
    }
  }

  return result;
}

 

---

3️⃣ 연속 부분수열 1

N개의 수로 이루어진 수열이 주어집니다.

이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N=8, M=6이고 수열이 다음과 같다면

1 2 1 3 1 1 1 2

합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

 

▣ 입력설명

첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.

수열의 원소값은 1,000을 넘지 않는 자연수이다.

 

▣ 출력설명

첫째 줄에 경우의 수를 출력한다.

 

▣ 입력예제 1

8 6

1 2 1 3 1 1 1 2

 

▣ 출력예제 1

3

---

투포인터 문제 중에서 가장 기본이 되는 문제이다.

논리는 어렵지 않지만 구현하는 과정에 까다로움을 느꼈다.

 

          

1

2

1

3

1

1

1

2

          

 

먼저 이 문제를 완전탐색을 이용해 해결한다고 생각하면,

배열의 0번째 인덱스부터 차례대로 나머지 인덱스들의 값끼리 더해가면서 부분합을 구해 6이 된다면 브레이크를 걸고 다음 인덱스로 넘어가서 또 나머지 인덱스들의 값끼리 부분합을 구하는 방법으로 구현할 수 있다.

 

투포인터를 이용한다면 첫번째 인덱스부터 시작해 6과 같은지 확인한다.

6보다 작기 때문에 계속해서 다음 인덱스로 옮겨가며 부분합을 구해야한다. 그렇기 위해서는 오른쪽 포인터를 한 칸 옆으로 옮겨준다.

 

          

1

2

1

3

1

1

1

2

                             

 

부분합은 이제 1+2 = 3이 된다.

이제 3과 6을 비교한다. 6보다 작기 때문에 부분합을 더 구해야한다. 계속해서 오른쪽으로 한 칸씩 옮겨보자.

 

          

1

2

1

3

1

1

1

2

                                                                   

 

오른쪽 포인터가 3을 가리키게 되면 부분합이 1+2+1+3 = 7이다.

6보다 크기 때문에 0번째 인덱스에서 부분합이 6을 만족하는 경우는 존재하지 않는다.

그렇기 때문에 이럴때는 왼쪽 포인터를 한 칸 옮겨준다. 이때 왼쪽 포인터가 가리키고 있는 값을 부분합에서 빼줘야한다.

이제는 다음 인덱스부터의 부분합을 구할 것이기 때문이다.

 

                               

1

2

1

3

1

1

1

2

                                                                   

 

자, 이제 부분합은 2+1+3 = 6이다. 드디어 찾았다.

부분합을 찾았으니 인덱스가 1인 경우에는 더 이상 부분합을 찾지 않아도 된다. 다음 인덱스로 넘어가야한다.

그렇기 때문에 왼쪽 포인터가 가리키는 값을 부분합에서 빼고, 왼쪽 포인터를 한 칸 옆으로 옮겨준다.

 

정리하자면 다음과 같다.

조건합을 m, 부분합을 sum이라고 하고, 왼쪽 포인터를 left, 오른쪽 포인터를 right라고 한다면

 

sum > m 이면 sum에서 arr[left]를 빼고 left를 +1 한다.

sum < m 이면 right를 +1하고 arr[right]의 값을 sum에 더한다.

sum = m 이면 sum에서 arr[left]를 빼고 left를 +1 한다.

 

이 과정을 오른쪽 포인터가 배열의 끝까지 다다라 더이상 가리키는 값이 없을 때까지 진행한다.

왜냐하면 더이상 부분합으로 조건합을 만족하는 경우의 수가 존재하지 않기 때문이다.

왼쪽 포인터를 끝까지 옮겨봤자 기존 부분합에서 왼쪽 포인터가 가리키는 값을 빼는 것이기 때문에 부분합은 항상 조건합보다 작을 수 밖에 없다.

---

구현 코드

위에서 언급한 논리의 과정을 코드로 구현하는 것이 까다롭다고 느꼈다.

하지만 반드시 구현의 단계까지 가야한다. 

function solution(m, arr) {
  let count = 0;
  let sum = 0;
  let left = 0;

  for (let right = 0; right < arr.length; right++) {
    sum += arr[right]; // 오른쪽 포인터가 가리키는 값을 부분합에 더함
    if (sum === m) count++; // 같다면 카운터를 증가
    while (sum >= m) {
      sum -= arr[left]; // 부분합이 같거나 크면 left가 가리키는 값만큼 부분합에서 빼고 left 증가
      left++;
      if (sum === m) count++; // 그리고 매 조건마다 조건합과 같은지 확인
    }
  }

  return count;
}

let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));

 

---

4️⃣ 연속 부분수열 2

연속 부분수열 2 N개의 수로 이루어진 수열이 주어집니다.

이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그 램을 작성하세요.

만약 N=5, M=5이고 수열이 다음과 같다면

1 3 1 2 3

합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}로 총 10가지입니다.

 

▣ 입력설명

첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.

수열의 원소값은 1,000을 넘지 않는 자연수이다.

 

▣ 출력설명

첫째 줄에 경우의 수를 출력한다.

 

▣ 입력예제 1

5 5

1 3 1 2 3

 

▣ 출력예제 1

10

---

내 풀이과정

right 포인터를 부분합에 더해서 부분합이 5보다 작으면 카운트를 하나씩 올려주고 right 포인터를 오른쪽으로 이동한다.

만일 부분합이 5보다 크게 된다면 left 포인터를 하나 올려주고 right 포인터를 left 포인터 위치로 이동시킨다.

그런다음에 부분합을 초기화하고 다시 위의 과정을 left 포인터가 배열의 모든 요소를 순회할 때까지 반복하면 된다.

function solution(m, arr) {
  let cnt = 0;
  for (let left = 0; left < arr.length; left++) {
    let sum = 0;
    let right = left;
    sum += arr[right];
    while (sum < m) {
      cnt++;
      right++;
      sum += arr[right];
    }
    if (sum === m) cnt++;
  }

  return cnt;
}

let a = [1, 3, 1, 2, 3];
console.log(solution(5, a)); // 10

 

강의 풀이

나의 풀이같은 경우에는 right 포인터를 다시 left 포인터로 이동시켜야했다. 

하지만 강의에서는 right 포인터를 left 포인터로 옮기지 않고 딱 한번 순회해서 구하는 방법이었다.

 

right 포인터가 가리키는 요소를 부분합에 더하며 5보다 작다면 카운트를 높여준다.

그리고 right 포인터를 오른쪽으로 이동시킨다.

그리고 부분합을 구해서 5보다 작은지 확인한다.

만일 해당 부분합이 5보다 작다는 것은 현재 right 포인터가 가리키는 값을 포함한 부분수열이 존재한다는 의미이기 때문에 부분수열의 갯수는 right - left + 1을 만족하게 된다.

 

예를 들면 부분 수열이 1,3 이고 m이 5이면 부분수열의 합은 m보다 작은 값이다.

그렇다면 3을 포함한 부분수열인 1,3 과 3이 존재한다는 것이다. 이 아이디어가 핵심이다.

 

function solution(m, arr) {
  let cnt = 0;
  let lt = 0;
  let sum = 0;
  for (let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    while (sum > m) {
      sum -= arr[lt++];
    }
    cnt += rt - lt + 1;
  }
  return cnt;
}

let a = [1, 3, 1, 2, 3];
console.log(solution(5, a)); // 10