투 포인터 알고리즘

두 개의 포인터 변수를 통해 문제를 해결하는 알고리즘

주로 그림 처럼 두 개의 배열에 순차적으로 접근 해야 할 때 두 개의 포인터 위치를 기록 하며 처리 하는 기법입니다.

문제

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

입력 설명

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

출력 설명

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

입력 예제

3
1 3 5
5
2 3 6 7 9

출력 예제

1 2 3 3 5 6 7 9

풀이

두 개의 배열이 입력으로 주어졌을 때, 그 배열의 값들을 기록하기 위한 포인터 변수(p1, p2)를 두고 각각 0으로 초기화 합니다.

그리고 arr1, arr2를 비교하게 되는데, 포인터 변수 값인 0번의 값을 서로 비교하여 더 작은 값을 answer에 추가 합니다.

arr1[0]은 1, arr2[0]은 2이기에 arr1이 더 작으므로 answer에 추가되고 p1의 포인터 변수가 1 증가 합니다.

p1이 1 p2가 0인 상태에서 다시 비교를 시작합니다. arr1[1]은 3이고 arr2[0]은 2이므로 2가 더 작기 때문에 arr2에 있는 2가 answer에 들어가고 p2가 1 증가 합니다.

이렇게 계속 비교하다보면 arr1을 모두 순회하게 되는데, 두 배열 중 하나라도 순회가 종료되면 남아있는 배열의 값들을 모두 순회하여 그대로 answer에 추가 합니다.

코드

function solution(A, B) {
  // 두 포인터 변수 p1, p2를 0으로 초기화
  let p1 = 0;
  let p2 = 0;
  let n = A.length;
  let m = B.length;
  let answer = [];
  // 포인터 변수가 각각 n, m 보다 커질 경우 종료
  while (p1 < n && p2 < m) {
    // 만약 A보다 B에 있는 값이 더 클 경우 A에 있는 값을 answer에 추가 후 p1 1증가(후위 증가)
    if (A[p1] <= B[p2]) answer.push(A[p1++]);
    // 만약 A가 더 클 경우 B에 있는 값을 answer에 추가 후 p2 1증가
    else answer.push(B[p2++]);
  }
  // 만약 A에서 answer에 추가 되어야 할 값이 있다면 마저 추가
  while (p1 < n) answer.push(A[p1++]);
  // 만약 B에서 answer에 추가 되어야 할 값이 있다면 마저 추가
  while (p2 < m) answer.push(B[p2++]);
  return answer;
}

console.log(solution([1, 3, 5], [2, 3, 6, 7, 9]));