효율성(투포인터 알고리즘) - 공통원소 구하기

문제

 

A, B 두 개의 집합의 교집합을 오름차순으로 구하시오

입력예제

1 3 9 5 2
3 2 5 7 8

출력예제

2 3 5

 

풀이

 

arr1의 배열과 arr2의 배열을 2중 for 문으로 탐색해도 가능하긴하다.

하지만 이는 시간복잡도가 n^2이라 비효율적이다.

 

여기서 투포인터 알고리즘을 사용해서 문제를 풀어볼것이다.

먼저 arr1과 arr2 배열을 오름차순(O(nlogn))으로 정렬한다.

그리고 arr1과 arr2를 비교하면서 각각의 배열의 index를 가리키는 값을 조절하면서

answer 배열에 요소를 push한다.

 

코드

 

function solution(arr1, arr2){
  let answer=[];
  let p1 = p2 = 0;
  arr1.sort((a,b) => a-b);  // 그냥 sort()를 해버리면 요소를 문자로 변환후에 사전순으로 정렬하게 된다.
  arr2.sort((a,b) => a-b);  // 그러므로 콜백함수에 (a, b) => a - b를 꼭 넣어서 숫자순으로 정렬하게 한다.
  
  while(p1 < arr1.length && p2 < arr2.length) {
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1]);
      p1++;
      p2++;
    } else if (arr1[p1] < arr2[p2]) { // arr1의 값이 작으면 p1값을 하나 올려준다
      p1++;
    } else if (arr1[p1] > arr2[p2]) { // 위와 반대로 한다.
      p2++;
    }
  }
  
  return answer;
}

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

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의