[인프런] Node.js / 섹션5-효율성(투포인터 알고리즘) / 2. 공통원소 구하기

A, B 두 개의 집합(중복 원소x)이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력

 

나의 풀이

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

  return answer;
}

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

투 포인터를 두고, p1을 기준으로 비교를 했다.

만약 p1과 p2 위치의 원소가 같다면, answer에 해당 인자를 넣고 p2를 0으로 초기화하고 p1은 그 다음 원소로 가고,

다르다면 p2를 다음 원소로 가서 비교를 한다.
만약 p2의 원소 끝까지 가면 p2를 0으로 초기화하고 p1을 다음 원소로 가도록 했다.
그리고 p1의 다음 인자가 더 이상 없으면 while문을 빠져나오고, sort로 오름차순으로 정렬을 하도록 했다.

 

강사 풀이

function solution(arr1, arr2) {
  let answer = [];
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);
  let p1 = (p2 = 0);
  while (p1 < arr1.length && p2 < arr2.length) {
    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(solution(a, b));

 

 

먼저 각 배열을 정렬함으로써 더 깔끔하게 풀으셨다.

그리고 나처럼 따로 기준 원소를 두지 않고 정석대로 잘 푸신 것 같다.

아직 내가 투 포인터를 정확히 아는 게 아니지만.. 해당 알고리즘 방식으로는 이렇게 푸는게 맞는 것 같다.