[알고리즘] 두 배열 합치기 - 투 포인터 (JavaScript)

구미·2021년 8월 25일

알고리즘 자바스크립트

알고리즘

목록 보기

22/25

✏️ 문제 설명

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

✏️ 입출력 예제

입력

3
1 3 5
5
2 3 6 7 9

출력

1 2 3 3 5 6 7 9

🔍 `sort`를 사용한 풀이

function solution(arr1, arr2) {
  const array = [...arr1, ...arr2];
  array.sort((a, b) => a - b);

  return array;
}

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

처음에는 스프레드 문법과 sort를 사용하여 정말 간단하게 풀었었는데 ㅋㅋㅋ
sort 함수를 사용하면 시간 복잡도가 O(NlogN)이 되기 때문에 O(N+M)이 될 수 있는 투 포인터를 사용해 문제를 푸는 것이 이 문제의 의도라고 한다 ㅎ

🔍 투 포인터를 사용한 풀이

function solution(arr1, arr2) {
  let p1 = 0;
  let p2 = 0;
  let value = 0;
  let answer = [];

  // 길이가 더 짧은 배열 탐색이 끝나면 아래 while문은 더이상 실행되지 않음
  while (p1 < arr1.length && p2 < arr2.length) {
    if (arr1[p1] < arr2[p2]) {
      answer.push(arr1[p1]);
      p1++;
    } else {
      answer.push(arr2[p2]);
      p2++;
    }
  }

  // 길이가 더 긴 배열의 남은 요소를 answer 배열에 담아주기
  while (p1 < arr1.length) {
    answer.push(arr1[p1]);
    p1++;
  }

  while (p2 < arr2.length) {
    answer.push(arr2[p2]);
    p2++;
  }

  return answer;
}

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