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

문제

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

 

문제풀이

각기 다른 두 배열을 하나의 배열로 합치기 위해 스프레드 연산자를 사용한다.

오름차순으로 정렬하기 위해 Array.sort() 메서드를 사용한다.

 

코드

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

  return answer;
}

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

 

문제풀이2

Array.sort() 메서드를 사용했을 경우 시간 복잡도는 O(n × logn)이어서 비효율적이다.

 

이를 대신에 투포인터 알고리즘을 사용하고자 한다.투포인터 알고리즘을 사용할 경우 단순 반복문을 k번 만큼(해당 문제에서는 2번)만 돌리면 되기 때문에 O(n+m)의 시간 복잡도가 나오기 때문에 더 효율적이다.

 

(해당 문제에서는 스프레드 연산을 하였기 때문에 n의 값이 1이기 때문에 그 차이가 미비하긴 하다)

 

임의의 두 포인터 변수 p1과 P2를 0으로 초기화 해준 뒤 각 해당 배열의 인덱스를 순회하며 값을 비교함으로써,

오름차순으로 구현할 수 있다.

 

코드

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

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

  return answer;
}

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