[JavaScript/section 5] 01 - 두 배열 합치기

📌 문제

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 문제이다.

 

📝 풀이

🧑🏻‍💻 나의 풀이 방법(강사님 풀이 방법과 동일😁)

두 배열을 하나로([...arr1, ...arr2]) 합치고 sort() 메서드를 사용하여 정렬함으로써 문제를 해결할 수도 있지만, sort() 메서드를 사용했을 경우 브라우저 엔진마다 다르지만 평균적으로 시간복잡도가 O(nlogn)에 해당한다. 이에 비해 투 포인터 알고리즘을 사용하면 시간복잡도는 O(n + m)이므로 매우 효율적이다.

 

• 포인터 p1, p2가 각 배열의 길이보다 작은 경우 while문을 돌며 arr1[p1]과 arr2[p2]를 비교한다.
• 오름차순으로 합쳐야 하므로 더 작은 값을 answer에 push() 메서드를 사용하여 삽입하고 해당 포인터를 1 증가시킨다.
• 포인터 하나가 배열의 길이만큼 이동했을 경우 while문을 빠져 나오고 나머지 배열의 포인터를 하나씩 이동하며 차례대로 answer에 삽입한다.

function solution(arr1, arr2) {
  let answer = [];
  let N = arr1.length;
  let M = arr2.length;
  let p1 = 0, 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 a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];
console.log(solution(a, b));