[JS] 코딩 테스트 문제 : 두 배열 합치기

문제 : 두 배열 합치기

문제 설명

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

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제 1

3
1 3 5
5
2 3 6 7 9

▣ 출력예제 1

1 2 3 3 5 6 7 9

내코드

function solution(arr1, arr2) {
  let answer = [];
  let arr1Index = 0;
  let arr2Index = 0;

  // O(n): two pointers algorithm
  // 두 배열을 계속해서 비교해가면서 큰값순서대로 배열에 집어넣는 방식
  // 1 번배열에의 값이 더 작다면 1번 배열의 index 를 1 증가시키는 방식
  for (let i = 0; i < arr1.length + arr2.length; i++) {
    // arr1 다 집어 넣은 경우 비교할 필요없이 arr2 내용을 집어넣음
    if (arr1[arr1Index] === undefined) {
      answer.push(arr2[arr2Index++]);
      continue;
    }

    // arr2 다 집어 넣은 경우 비교할 필요없이 arr1 내용을 집어넣음
    if (arr2[arr2Index] === undefined) {
      answer.push(arr1[arr1Index++]);
      continue;
    }

    // arr1 같거나 더 작으면 arr1 내용 삽입 (값이 같은 경우 arr1 내용을 넣도록 설정)
    if (arr1[arr1Index] <= arr2[arr2Index]) {
      answer.push(arr1[arr1Index]);
      arr1Index++;
    } else {
      answer.push(arr2[arr2Index]);
      arr2Index++;
    }
  }

  // O(n logn) 방식
  // answer = [...arr1, ...arr2].sort((a, b) => a - b);
  return answer;
}

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

풀이

1. 이미 정렬된 두 배열에 각각의 인덱스값 0 을 지정 (투 포인트 개념)
2. 각 배열의 index 번의 숫자와 비교해 더 작은 숫자값은 저장하고 그 배열의 index 를 증가시킨다.

보완할 수 있는 부분

// 현재 코드
for (let i = 0; i < arr1.length + arr2.length; i++) {
  // arr1 다 집어 넣은 경우 비교할 필요없이 arr2 내용을 집어넣음
  if (arr1[arr1Index] === undefined) {
    answer.push(arr2[arr2Index++]);
    continue;
  }

  // arr2 다 집어 넣은 경우 비교할 필요없이 arr1 내용을 집어넣음
  if (arr2[arr2Index] === undefined) {
    answer.push(arr1[arr1Index++]);
    continue;
  }

  // arr1 같거나 더 작으면 arr1 내용 삽입 (값이 같은 경우 arr1 내용을 넣도록 설정)
  if (arr1[arr1Index] <= arr2[arr2Index]) {
    answer.push(arr1[arr1Index]);
    arr1Index++;
  } else {
    answer.push(arr2[arr2Index]);
    arr2Index++;
  }
}

// 보완 코드
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;

1. 기존 코드에서는 1번 2번 배열 값 만큼 for 문을 돌렸고
2. 보완 코드 부분에서는 while 문으로 1번 2번 배열 중 index 가 최대치만큼 이동한 경우 까지 반복 후 다음 while 문에서 나머지 내용 다 넣어주고 마친다. (좀 더 간결)

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard