11728 배열 합치기

간단한 풀이

const [tc, ...input] = require('fs')
  .readFileSync('dev/stdin')
  .toString()
  .trim()
  .split('\n');
const a = input[0].split(' ').map(Number);
const b = input[1].split(' ').map(Number);
const answer = [...a, ...b].sort((a, b) => a - b);
console.log(answer.join(' '));

위와 같이 간단하게 spread 문법과 sort 함수를 사용해 문제를 해결할 수도 있다.

하지만 sort 메소드는 O(n log(n))의 시간복잡도를 갖기 때문에 처리시간이 오래걸린다.

시간복잡도를 단축하기 위해 직접 반복문을 사용해 다음과 같이 개선했다.

속도 개선 코드

시간복잡도 O(n)

const input = require('fs').readFileSync('./input.txt').toString().trim().split('\n');
const [n, m] = input.shift().split(' ').map(Number);
const a = input[0].split(' ').map(Number);
const b = input[1].split(' ').map(Number);

let checkA = 0;
let checkB = 0;
const answer = [];

for (let i = 0; i < n + m; i++) {
  if (n === checkA) answer.push(b[checkB++]); // 1
  else if (m === checkB) answer.push(a[checkA++]); // 2
  else if (a[checkA] <= b[checkB]) answer.push(a[checkA++]); // 3
  else answer.push(b[checkB++]); // 3
}
console.log(answer.join(' '));

두 배열을 비교해 더 작은 수부터 answer 배열에 삽입하는 방식으로 구현했다.

checkA 와 checkB 변수는 각 배열의 비교할 인덱스를 갖게된다.

1. a 배열의 마지막 요소까지 도달했다면 b 배열과 비교할 필요가 없으므로 b 배열의 원소를 answer에 삽입한다.

2. 반대로 b 배열의 마지막 요소까지 도달했다면 a 배열 원소를 answer에 삽입한다.

3. 각 배열의 checkA(또는B) 원소끼리 비교해 작은 수를 answer에 삽입한다.

   이 조건문이 실행된다는 것은 두 배열 모두 마지막 요소까지 도달하지 못했다는 의미