📌강의 정리
문제 자체는 어렵지 않다.
sort함수를 쓰기만 해도 nlog(n)이므로 시간복잡도가 높아진다.
하지만 투포인터를 쓰면 O(n+m)으로 끝낼 수 있다.
두 개의 포인터를 잡았다고 투포인터 알고리즘이다.
answer라는 배열을 잡아서 계속 push를 하면 된다.
두 개의 arr1,2를 비교해서 작은 것을 앤서배열에 넣는다.
arr1[p1] 과 arr2[p2]를 비교한다. 이때의 p1,p2가 포인터이다.
넣으면 포인터를 1 증가시킨다.
이렇게 계속 비교해서 한쪽이 끝나면 한쪽은 남으므로 그것을 그냥 다
집어넣으면 된다.
n,m을 길이로 해놓고 p1,p2도 0으로 설정해 놓는다.
while(p1<n && p2<m)을 하면 둘 중 아무거나 끝나면 반복문이 끝나게
설정할 수 있다.
if(arr[p1]≤arr2[p2]) answer.push(arr[p1++]);
p1++이면 후치연산이므로 일단 넣어지고 그다음 ++된다.
else answer.push(arr2[p2++])
이다. 이제 반복문이 끝나고 arr1,arr2중 어떤게 끝난는지 알아보고
남은걸 다 집어 넣어야 하므로
while(p1<n) answer.push(arr1[p1++]);
while(p2<n) answer.push(arr1[p2++]);
로 하면 남은걸 다 넣을 수 있다.
📌느낀점
프로그래머스 문제를 풀다보면 시간이 오래걸려 틀릴때가
종종 있었는데 이문제 였던 것 같다.
여기서는 sort로 풀면 간단하지만 시간복잡도를 위해 answer배열에 작은 것을
순서대로 포인터를 이용해서 집어넣는다.
투포인터의 기초중 기초이므로 잘 기억해둬야겠다.
//나의 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(arr1, arr2){
let answer = arr2;
for(let x of arr1){
answer.push(x)
}
answer.sort(function(a,b){
return a-b;
})
return answer;
}
let a=[1, 3, 5];
let b=[2, 3, 6, 7, 9];
console.log(solution(a, b));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
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];
let b=[2, 3, 6, 7, 9];
console.log(solution(a, b));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 5. 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)' 카테고리의 다른 글
| 6.학급 회장(Hash Map) (0) | 2022.06.18 |
|---|---|
| 5.최대 매출(Sliding Window) (0) | 2022.06.17 |
| 4.연속부분수열2(Two Pointers Algorithm) (0) | 2022.06.16 |
| 3.연속부분수열1(Two Pointers Algorithm) (0) | 2022.06.15 |
| 2.공통원소구하기(Two Pointers Algorithm) (0) | 2022.06.14 |