효율성

자릿수의 합

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

• 입력설명
  첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
  두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
  세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
  네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
  각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다

• 출력설명
  오름차순으로 정렬된 배열을 출력합니다.

• 입력예제

3
1 3 5
5
2 3 6 7 9

• 출력예제

1 2 3 3 5 6 7 9

• 답안1

//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";

const input = fs.readFileSync(`${filePath}`).toString().trim().split("\r\n");

//solution함수 안에 답안을 작성하세요.
function solution(input) {
  const firstArr = input[1].split(" ").map(Number);
  const secondArr = input[3].split(" ").map(Number);
  const answer = [];

  while (true) {
    if (!firstArr.length || !secondArr.length) {
      // 만일 두 배열 중 하나라도 비어있으면 정답에 배열을 합친 후 종료한다.
      answer.push(...firstArr, ...secondArr);
      console.log(answer.join(" "));
      break;
    } else if (firstArr[0] < secondArr[0]) {
      //배열 중 작은 숫자를 shift해서 answer에 추가한다.
      answer.push(firstArr.shift());
    } else {
      answer.push(secondArr.shift());
    }
  }
}

solution(input);

• 풀이 해설
  while 문을 이용하여 배열의 가장 앞의 값을 비교한 후, 작은 값을 shift로 반환한다. 만일 두 배열 중 하나라도 길이가 0이 되면 배열들을 정답에 합친 후 정답을 출력하고 while문을 탈출한다.
  해당 답안의 문제는 shift를 사용한다는 점이다. shift는 O(n)의 시간 복잡도를 가질 수 있다.
  포인터를 이용하여 아래와 같이 수정할 수 있다.

• 답안2 (포인터를 이용한 답안)

//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";

const input = fs.readFileSync(`${filePath}`).toString().trim().split("\r\n");

//solution함수 안에 답안을 작성하세요.
function solution(input) {
  const firstArrLength = Number(input[0]);
  const firstArr = input[1].split(" ").map(Number);
  const secondArrLength = Number(input[2]);
  const secondArr = input[3].split(" ").map(Number);
  const answer = [];

  //포인터를 만든다
  let firstIdx = 0;
  let secondIdx = 0;

  //두 배열 중 하나라도 포인터가 마지막에 닿으면 반복문을 종료한다.
  while (firstIdx < firstArrLength && secondIdx < secondArrLength) {
    //두 배열 중 포인터가 가르키는 값을 비교하여 작은 값을 답에 push하고 해당하는 포인터를 오른쪽으로 이동한다.
    if (firstArr[firstIdx] < secondArr[secondIdx]) {
      answer.push(firstArr[firstIdx]);
      firstIdx = firstIdx + 1;
    } else {
      answer.push(secondArr[secondIdx]);
      secondIdx = secondIdx + 1;
    }
  }

  //포인터를 기준으로 마지막까지의 값들을 answer에 push한다.
  //해당 과정은 slice메서드가 아닌 for문으로 대체하여 공간복잡도를 줄일 수 있다.
  answer.push(...firstArr.slice(firstIdx, firstArrLength));
  answer.push(...secondArr.slice(secondIdx, secondArrLength));
  console.log(answer.join(" "));
}

solution(input);

• 자바스크립트 문법 팁
  Array.Prototype.slice(시작인덱스, 마지막 인덱스) : slice는 마지막 인덱스 '전'까지 반환함에 유의하며 사용하자. slice는 기존 배열을 얕은 복사하여 새로운 배열을 반환한다.