티스토리 뷰
문제
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램
을 작성하세요.
풀이
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
링크
TAG
- 위코드
- React
- 아차산
- nodejs
- 노개북
- createPortal
- NextApiRequest
- error
- C언어
- jest
- electron
- 우아한테크코스
- env
- 노마드코더
- javascript
- 윤성우 열혈C프로그래밍
- Storybook
- 프리온보딩
- 북클럽
- 원티드
- nextjs
- 초보
- NextRequest
- 프론트앤드
- TopLayer
- 스토리 북
- WSL2
- CLASS
- import/order
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함