투 포인터 알고리즘

개요

완전탐색으로 풀면 시간복잡도가 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]));