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

문제

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

 

문제풀이

두 배열을 합쳐 초기화 한 임의 변수를 순회하면서 Array.indexOf() 메서드와 인덱스 i를 사용하여 해당 요소의 인덱스 값을비교한다. 

 

Array.indexOf() 메서드는 중복되는 요소가 여러 개 있다면 첫 번째로 검색된 요소의 인덱스를 반환하기 때문에 중복 된 값을식별할 수 있다.

 

코드

function solution(arr1, arr2) {
  let answer = [];
  let tmp = [...arr1, ...arr2];

  tmp.forEach((item, i) => {
    if(tmp.indexOf(item) !== i) {
      answer.push(item);
    }
  })
  console.log(tmp)

  answer.sort((a, b) => a - b);

  return answer;
}

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

 

문제풀이2

사전에 오름차순으로 정렬 된 각 배열을 반복문 내에서 임의의 포인터 변수를 통해 중복된 값을 식별한다.

 

이때 배열의 원소들은 오름차순으로 정렬되어 있기 때문에 포인터 변수로 가리킨 값 중 작은 값에 해당하는 배열의포인터 변수를 다음 인덱스를 가리키게 해준다.

 

오름차순 특성 상 큰 값에 해당하는 배열의 포인터 변수를 이동하게 될 경우 이 값보다 작은 값(공통원소일 수 있는 값)을 이후 인덱스 요소 내에서 찾을 수 없기 때문이다.

 

코드

function solution(arr1, arr2) {
  let answer = [];
  arr1.sort();
  arr2.sort();
  let p1 = 0;
  let 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 arr1 = [1, 3, 9, 5, 2];
let arr2 = [3, 2, 5, 7, 8];
console.log(solution(arr1, arr2));