[인프런] Node.js / 섹션5-효율성(투포인터 알고리즘) / 1. 두 배열 합치기

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력

 

나의 풀이

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

  return answer;
}

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

나는 투포인터 방식이 아니라 그냥 sort를 이용해 풀었다.

sort의 시간복잡도는 O(nlogn)라고 한다.

 

sort로 오름차순으로 정렬할 때 주의해야할 점은, sort()가 아닌 sort((a-b) => {a-b}) 으로 해줘야한다.

sort()만 하면 문자열로 변환해서 사전순으로 정렬하기 때문에, 두 자리수 이상인 숫자를 비교할 때 원하지 않는 결과가 나오게 된다. 그래서 후자처럼 해줘야한다.

 

 

강사 풀이

function solution2(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 a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];
console.log(solution2(a, b));

투 포인터를 이용해서 풀으셨다.

 

포인터를 두개 두고, 두 배열을 비교해서 작은걸 answer에 넣고 해당 포인터를 1증가 시킨다.

한 배열을 다 탐색하면 비교하는걸 멈추고 나머지 배열을 다 answer에 넣으면 끝이다. 더이상 비교할 게 없고, 이미 오름차순으로 정렬되어있기 때문이다.