(알고리즘) 두 배열 합치기

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

입력설명

요소들이 오름차순으로 정렬된 두 배열이 주어진다.

출력설명

오름차순으로 정렬된 배열을 출력한다.

입력예제

• [1, 3, 5]
• [2, 3, 6, 7, 9]

출력예제

[1, 2, 3, 5, 6, 7, 9]

원래 문제는 아주 간단하게 두 배열을 합치는 것이었지만, 한 번 더 꼬아서 중복을 제거하는 규첵을 추가해보았다.
이 문제는 3개의 풀이방식으로 풀이가 가능하다.

• 내장함수 filter를 이용해 요소들의 인덱스 값을 비교하는 방식으로 리턴문 반환하기

function solution(arr1, arr2) {
  let answer = [];
  const temp = arr1.concat(arr2).sort((a, b) => a - b);
  return answer = temp.filter((item, index) => {
    return temp.indexOf(item) === index;
  });
}

• 객체에 값을 담고, 객체의 키값을 반환하는 방식

function solution2(arr1, arr2) {
  let answer;
  let objUnique = {};
  const temp = arr1.concat(arr2).sort((a, b) => a - b).forEach((item) => {
    objUnique[item] = true; 
  });
  return answer = Object.keys(objUnique);
}

• 가장 간편한 방식이다. set과 스프레드 오퍼레이터를 이용하기

function solution3(arr1, arr2) {
  let answer;
  const temp = arr1.concat(arr2).sort((a, b) => a - b);
  return answer = [...new Set(temp)];
}

3가지 모두 아주 잘 작동한다 😇

Advance

위 문제풀이는 시간 복잡도가 고려되지 않은 문제 풀이다. 당장 sort함수를 호출했을 때 시간복잡도는 nlogn이 되기 때문에, 시간 복잡도를 따지는 일부 코딩 테스트에는 통과되지 않을 수 있다.

시간 복잡도를 고려한다면, two pointer algorithm을 고려해볼만 하다.
2개의 포인터는 n + n의 시간복잡도를 갖는다.

투 포인터 알고리즘
1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다.

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] <= app2[p2]) {
      answer.push(arr1[p1++]);
    } else {
      answer.push(arr2[p2++]);
    }
  }
  while(p1 < n) {
    answer.push(arr1[p1++]);
  }
  while(p2 < m) {
    answer.push(arr2[p2++]);
  }
}