[알고리즘] 공통원소 구하기 - 투포인터 알고리즘

문제

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

(두 집합의 공통원소를 오름차순 정렬하여 출력합니다.)

입력예제

5
1 3 9 5 2
5
3 2 5 7 8

풀이

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

    return answer;
  }

  let a = [1, 3, 9, 5, 2];
  let b = [3, 2, 5, 7, 8];
  console.log(solution2(a, b));

• p1, p2의 두개의 포인터가 있을 때, 가리키는 값을 비교해 더 작은 쪽의 포인터를 증가하여 이동시킨다.
• 작은 쪽을 가리키고 있다는 것은 비교중인 다른 배열에는 그보다 작거나 같은 값이 없다는 의미이기 때문이다. 
• p1, p2가 가리키는 값이 같을 경우 p1과 p2를 동시에 증가시킨다.

 

나의 풀이 

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

    return answer;
  }

  let a = [1, 3, 9, 5, 2];
  let b = [3, 2, 5, 7, 8];
  //console.log(solution(a, b));

• 나는 하나의 포인터만 이동시키면서, 같은 값이 나오면 그 값을 answer.push 하고 비교중인 배열의 해당 요소를 splice로 삭제했다.