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

A, B 두 집합의 공통 원소를 추출하여 오름차순으로 출력

입력예제

집합 A는 N(1<=N<=30,000)개의 원소가 중복되지 않게 주어진다.
집합 B는 M(1<=M<=30,000)개의 원소가 중복되지 않게 주어진다.

각 집합의 원소는 1,000,000,000이하의 자연수입니다.

function solution2(p1,p2) {
    let result = [];
    let a = 0, b = 0;
    
    // 두 배열 모두 오름차순으로 정렬하여 비교
    p1.sort((a,b)=>a-b);
    p2.sort((a,b)=>a-b);
  
    // 두 배열 중 짧은 길이의 배열까지 while문 
    while(a<p1.length && b<p2.length) {
        
      if(p1[a]===p2[b]) {
            result.push(p1[a++]);
            b++;
        }else if(p1[a]<p2[b]) a++;
        else b++;
    }

    return result;
}

let arr3 = [1,3,9,5,2];
let arr4 = [3,2,5,7,8];

console.log(solution2(arr3,arr4));  // [2,3,5]

• 오름차순으로 정렬한 뒤 0번째 배열부터 비교하며 같은 원소만 push

• 오름차순으로 정렬되어 있기 때문에 더 작은 숫자가 있는 배열의 순번을 ++시킨 뒤 다시 비교한다.

p1 : 1,2,3,5,9
p2 : 2,3,5,7,8
1. 0번째 배열 1, 2를 비교 => 더 작은 숫자가 있는 p1의 순번을 ++
2. p1의 1번 배열 2와 p2의 0번 배열 비교
  => 숫자가 같기 때문에 push, p2의 순번 ++
3. 두 배열 중 짧은 길이의 배열까지 while문을 돌리며 공통 원소를 추출

더 긴 배열의 나머지 원소는 자연스럽게 공통된 숫자가 아니기 때문에 의미가 없다!