728x90
๋ฐ์ํ
๐ ๋ฌธ์
์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ์ด ๋ ๋ ๋ฐฐ์ด์ด ์ฃผ์ด์ง๋ฉด ๋ ๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ํฉ์ณ ์ถ๋ ฅํ๋ ๋ฌธ์ ์ด๋ค.
๐ ํ์ด
๐ง๐ป๐ป ๋์ ํ์ด ๋ฐฉ๋ฒ(๊ฐ์ฌ๋ ํ์ด ๋ฐฉ๋ฒ๊ณผ ๋์ผ๐)
๋ ๋ฐฐ์ด์ ํ๋๋ก([...arr1, ...arr2]) ํฉ์น๊ณ sort() ๋ฉ์๋๋ฅผ ์ฌ์ฉํ์ฌ ์ ๋ ฌํจ์ผ๋ก์จ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์๋ ์์ง๋ง, sort() ๋ฉ์๋๋ฅผ ์ฌ์ฉํ์ ๊ฒฝ์ฐ ๋ธ๋ผ์ฐ์ ์์ง๋ง๋ค ๋ค๋ฅด์ง๋ง ํ๊ท ์ ์ผ๋ก ์๊ฐ๋ณต์ก๋๊ฐ O(nlogn)์ ํด๋นํ๋ค. ์ด์ ๋นํด ํฌ ํฌ์ธํฐ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ฉด ์๊ฐ๋ณต์ก๋๋ O(n + m)์ด๋ฏ๋ก ๋งค์ฐ ํจ์จ์ ์ด๋ค.
- ํฌ์ธํฐ p1, p2๊ฐ ๊ฐ ๋ฐฐ์ด์ ๊ธธ์ด๋ณด๋ค ์์ ๊ฒฝ์ฐ while๋ฌธ์ ๋๋ฉฐ arr1[p1]๊ณผ arr2[p2]๋ฅผ ๋น๊ตํ๋ค.
- ์ค๋ฆ์ฐจ์์ผ๋ก ํฉ์ณ์ผ ํ๋ฏ๋ก ๋ ์์ ๊ฐ์ answer์ push() ๋ฉ์๋๋ฅผ ์ฌ์ฉํ์ฌ ์ฝ์ ํ๊ณ ํด๋น ํฌ์ธํฐ๋ฅผ 1 ์ฆ๊ฐ์ํจ๋ค.
- ํฌ์ธํฐ ํ๋๊ฐ ๋ฐฐ์ด์ ๊ธธ์ด๋งํผ ์ด๋ํ์ ๊ฒฝ์ฐ while๋ฌธ์ ๋น ์ ธ ๋์ค๊ณ ๋๋จธ์ง ๋ฐฐ์ด์ ํฌ์ธํฐ๋ฅผ ํ๋์ฉ ์ด๋ํ๋ฉฐ ์ฐจ๋ก๋๋ก answer์ ์ฝ์ ํ๋ค.
function solution(arr1, arr2) {
let answer = [];
let N = arr1.length;
let M = arr2.length;
let p1 = 0, 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];
let b = [2, 3, 6, 7, 9];
console.log(solution(a, b));
'Algorithm > ์ธํ๋ฐ(inflearn)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JavaScript/section 5] 03 - ์ฐ์ ๋ถ๋ถ ์์ด 1 (0) | 2022.09.19 |
---|---|
[JavaScript/section 5] 02 - ๊ณตํต์์ ๊ตฌํ๊ธฐ (0) | 2022.09.18 |
[JavaScript/section 4] 05 - K๋ฒ์งธ ํฐ ์ (0) | 2022.09.16 |
[JavaScript/section 4] 04 - ์กธ์ ์ ๋ฌผ (0) | 2022.09.15 |
[JavaScript/section 4] 03 - ๋ฉํ ๋ง (0) | 2022.09.14 |