완전탐색으로 풀면 시간복잡도가 O(N^2)이 되는데 투포인터로 풀면 O(N)이 된다.
두개의 포인터를 두어, 배열의 끝까지 이동 시키면서 주어진 조건을 만족하는 값을 새로운 배열에 push
하는게 관건이다.
const solution = (n,arr_1,m,arr_2) => {
const answer = [];
let pointer_1 = 0;
let pointer_2 = 0;
// 배열 전부 오름차순 정렬
arr_1.sort();
arr_2.sort();
// 포인터가 배열 끝에 도달하면 종료
while (pointer_1 < n && pointer_2 < m) {
// 포인터가 가리키는 두 배열의 요소가 같을 때, 정답에 추가
if (arr_1[pointer_1]===arr_2[pointer_2]){
answer.push(arr_1[pointer_1]);
pointer_1++;
pointer_2++;
// 두 배열 모두 오름차순 정렬을 했기 때문에, 포인터가 가리키는 곳 중에 한곳이 더 작으면, 작은 쪽의 포인터 인덱스를 늘려줘야 한다.
} else if (arr_1[pointer_1] < arr_2[pointer_2]) {
pointer_1++;
// 위의 반대 경우
} else {
pointer_2++;
}
}
return answer;
}
console.log(solution(5,[1,3,9,5,2],5,[3,2,5,7,8]));