[JS] 알고리즘 기초 정복 5-1번_두 배열 합치기

문제 5-1번

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

 

🍄 입력설명

첫 번째 줄에 첫 번째 배열의 크기 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

 

---

정답 코드

 - sort함수를 써서 간단하게 구현하려 했으나,, sort 함수의 시간 복잡도는 nlogn 이다. 

function solution(arr, arr2) {
	let answer = arr.concat(arr2);
	answer.sort((a, b) => a - b);

	return answer;
}

let arr = [1, 3, 5];
let arr2 = [2, 3, 6, 7, 9];
console.log(solution(arr, arr2));
// (8) [1, 2, 3, 3, 5, 6, 7, 9]출력

 

 - 투포인터 알고리즘, for문을 두번 돌면 O(n + m)의 시간복잡도를 가진다. 

function solution(arr, arr2) {
	let answer = [];
	let n = arr.length;
	let m = arr2.length;
	let p1 = (p2 = 0);
	// 포인터를 두개 잡는다. = 투 포인터 알고리즘 p1=p2=0;
	//둘중에 아무거나 거짓이 되더라도 멈춰야하므로 && 다
	while (p1 < n && p2 < m) {
		if (arr[p1] <= arr2[p2]) answer.push(arr[p1++]);
		//arr1에 push한 후 p1을 ++ 하라는 뜻
		else answer.push(arr2[p2++]);
	}
	//p2가 다 끝났을 경우,
	while (p1 < n) answer.push(arr[p1++]);
    //p1이 다 끝났을 경우,
	while (p2 < m) answer.push(arr2[p2++]);

	return answer;
}

let arr = [1, 3, 5];
let arr2 = [2, 3, 6, 7, 9];
console.log(solution(arr, arr2));
// (8) [1, 2, 3, 3, 5, 6, 7, 9]출력