(알고리즘) 공통원소 구하기 : 투포인터 (Two Pointer) 알고리즘

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출해 오름차순으로 출력하는 프로그램을 작성하세요.

출력설명

두 집합의 공통원소를 오름차순 정렬해 출력한다.

입력예제

• [1, 3, 9, 5, 2]
• [3, 2, 5, 7, 8]

투포인터 알고리즘

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다.
• 정렬되어 있는 두 리스트의 합집합에도 사용된다. 병합정렬(merge sort)의 conquer 영역의 기초가 된다.
  출처 더 보기

이중 for문을 순회하면서 문제 풀기 : 시간 복잡도 n제곱

function solution(arr1, arr2) {
  let answer = [];
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) {
        answer.push(arr1[i]);
      }
    }
  }
  return answer.sort((a, b) => a - b);
}

const arr1 = [1, 3, 9, 5, 2];
const arr2 = [3, 2, 5, 7, 8];

console.log(solution(arr1, arr2));

투 포인터 알고리즘을 이용해 문제 풀기 : 시간 복잡도 2n

function solution(arr1, arr2) {
  let answer = [];
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);
  const n = arr1.length;
  const m = arr2.length;
  let p1=p2=0;
  
  while (p1 < n && p2 < m) {
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1++]);
      p2++
    } 
    else if (arr1[p1] < arr2[p2]) p1++;
    else p2++;
  }
  return answer;
}

const arr1 = [1, 3, 9, 5, 2];
const arr2 = [3, 2, 5, 7, 8];

console.log(solution(arr1, arr2));