효율성(투포인터 알고리즘) - 두 배열 합치기

문제

 

오름차순으로 정렬된 두 배열이 주어지면
두 배열을 오름차순으로 합쳐 출력하는 함수 만들어보기

 

let a=[1, 3, 5]; (조건: 각 리스트의 원소는 int형 변수)
let b=[2, 3, 6, 7, 9];
console.log(solution(a, b));

 

출력예제

1 2 3 3 5 6 7 9

 

 

풀이

 

이 문제를 단순하게 아래처럼 한 배열에 넣고 sort를 돌리면 문제의 의도와 맞지가 않다.

sort는 시간복잡도가 n log n이 걸린다.

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

 

투 포인터 알고리즘은 두 배열을 한 번씩만 훑기 때문에

시간복잡도는 배열의 길이 n + 다른 배열의 길이 m 이다.

더 효율적이다.

 

코드

 

function solution(arr1, arr2){
  let answer = [];
  let n = arr1.length;
  let m = arr2.length;
  let p1 = 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));

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의