배열 합치기

문제

백준 11728번 - 배열 합치기

언어

JavaScript

순서도

left 와 right 두 포인터 선언
left 는 배열 A 를 순회하고, right 는 배열 B 를 순회하며, 두 배열 중 더 작은 값을 우선적으로 결과 배열에 삽입
둘 중의 하나의 배열을 모두 순회했다면, 나머지 배열을 순회하며 결과 배열에 삽입
결과 배열을 문자열 형태로 변환 후 출력

문제 풀이 step 1

두 포인터 형식의 문제로 두 개의 포인터를 선언하고 조작하며 문제에서 원하는 결과를 출력하는 문제입니다.
정렬된 두 배열 A 와 B 를 합친 다음 정렬해서 출력하는 문제입니다.
- 정직하게 두 배열을 합친 후 sort 함수를 이용해서 정렬하는 방법도 있지만, 이렇게 하면 시간이 오래 걸립니다.
두 배열이 정렬되어 있기 때문에 두 포인터를 이용해서 풀 수 있습니다.
- 하나의 포인터는 배열 A 를 순회하고, 다른 하나의 포인터는 배열 B 를 순회합니다.
- 우선 둘 중의 하나의 포인터가 끝에 도달할 때까지 배열을 순회하며, 두 배열의 값 중에서 더 작은 값을 결과 배열에 담습니다.
- 그리고 하나의 포인터가 끝에 도달해서 반복문이 종료되면, 다른 하나의 포인터가 끝에 도달할 때까지 순회하며 배열의 값들을 결과 배열에 담습니다.
결과 배열을 문자열의 형태로 변환 후 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

정렬 방식이 Merge Sort 의 한 부분과 닮아 있어서 참고하면 좋을 것 같습니다.
while 문은 반복문이며, 조건문으로도 사용될 수 있다는 사실을 잊지 말자!!

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [a, b] = input[0].split(" ").map(Number);
	const aArr = input[1].split(" ").map(Number);
	const bArr = input[2].split(" ").map(Number);

	const res = [];
	// 두 포인터 선언
	let [left, right] = [0, 0];
	while (left < a && right < b) {
		// 두 포인터가 각 배열을 순회하며, 더 작은 값을 결과 배열에 담습니다.
		if (aArr[left] <= bArr[right]) {
			res.push(aArr[left++]);
		} else {
			res.push(bArr[right++]);
		}
	}

	// 두 포인터 중에서 하나의 포인터가 끝에 도달했고,
	// 다른 포인터도 순회하며 값을 결과 배열에 담습니다.
	while (right < b) {
		res.push(bArr[right++]);
	}
	while (left < a) {
		res.push(aArr[left++]);
	}

	// 문자열 형태로 변환 후 출력
	return res.join(" ");
};

console.log(solution(input));