티스토리 뷰

알고리즘/코딩테스트 공부

5-1 두 배열 합치기

YG - 96년생 , 강아지 있음, 개발자 희망 2021. 12. 1. 13:28

문제

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

풀이

function solution(arr1, arr2) {
  let answer = [];
  let n = arr1.length;
  let m = arr2.length;
  for (let i = 0; i < n; i++) {
    answer.push(arr1[i]);
  }
  for (let i = 0; i < m; i++) {
    answer.push(arr2[i]);
  }
  answer = answer.sort((a, b) => a - b);
  console.log(answer);
  return answer;
}

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

배열을 합친뒤 sort를 이용하는 방식으로 풀었으나 시간복잡도가 n+m 그리고  sort의 시간복잡도 n log n 까지 더해져 시간적인 측면에서 비효율적인 방식입니다.

 

 

다른 풀이

function solution(arr1, arr2) {
  let answer = [];
  let n = arr1.length;
  let m = arr2.length;
  let p1 = (p2 = 0);
  let cnt = 0;
  while (cnt < n + m) {
    if (arr1[p1] <= arr2[p2]) {
      answer.push(arr1[p1]);
      p1++;
    } else if (arr1[p1] >= arr2[p2]) {
      answer.push(arr2[p2]);
      p2++;
    } else if (arr1[p1] === undefined) {
      answer.push(arr2[p2]);
      p2++;
    } else if (arr2[p2] === undefined) {
      answer.push(arr1[p1]);
      p1++;
    }
    //console.log(arr1[p1], arr2[p2]);
    //console.log(p1, p2);
    cnt++;
  }
  return answer;
}

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

투포인트 정렬로 풀었습니다. 

다른 풀이

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, 7, 9, 11, 13, 15];
let b = [2, 3, 6, 7, 9];
console.log(solution(a, b));

투포인트 정렬이나 코드를 간력히 한 방식입니다.

'알고리즘 > 코딩테스트 공부' 카테고리의 다른 글

5-3 연속 부분수열 1  (0) 2021.12.01
5-2 공통원소 구하기  (0) 2021.12.01
4-5 K번째 큰 수  (0) 2021.11.28
4-3 멘토링  (0) 2021.11.28
4-2 뒤집은 소수  (0) 2021.11.28
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함