TIL. 투 포인터 알고리즘 문제풀이2

공통원소 구하기

문제 설명

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

▣ 입력설명
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다. 두 번째 줄에
N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 세 번째 줄에
집합 B의 크기 M(1<=M<=30,000)이 주어집니다. 네 번째 줄에 M개의 원소가
주어집니다. 원소가 중복되어 주어지지 않습니다. 각 집합의 원소는
1,000,000,000이하의 자연수입니다.

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

▣ 입출력 예

input	output
5 / 1 3 9 5 2 / 5 / 3 2 5 7 8	2 3 5

풀이

소수찾기일 경우

const isPrime = (num) => {
  if (num <= 1) {
    return false;
  }
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
};

const commonElements = (a, b) => {
  const arrA = a.sort((x, y) => x - y);
  const arrB = b.sort((x, y) => x - y);
  const answer = [];

  for (let i = 0; i < a.length; i++) {
    if (isPrime(arrA[i]) && arrB.includes(arrA[i])) answer.push(arrA[i]);
  }

  return answer;
};

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

👉 두 배열에서 공통된 소수 원소를 찾는 코드를 작성했다.

• 각 배열을 오름차순으로 정렬한다.
• 배열 A의 각 원소가 소수인지 확인하고 배열 B에도 동일한 원소가 존재하는지 확인한다.
• 시간 복잡도는 O(N제곱)으로, 두 배열의 길이가 매우 길다면 성능에 문제가 생길 수도 있다! 🧐

투포인터 알고리즘 활용하기

📌 두 포인터 i와 j를 사용하여 풀이
arrA[i]와 arrB[j]가 같으면: 두 원소는 공통 원소이므로 결과 배열에 추가되고, 두 포인터 모두 다음 원소로 이동

arrA[i]가 arrB[j]보다 작으면: arrA의 현재 원소는 arrB에 없으므로, i만 증가시켜 다음 원소로 이동

arrA[i]가 arrB[j]보다 크면: arrB의 현재 원소는 arrA에 없으므로, j만 증가시켜 다음 원소로 이동

const commonElements = (a, b) => {
  const arrA = a.sort((x, y) => x - y); // [1,2,3,5,9]
  const arrB = b.sort((x, y) => x - y); // [2,3,5,7,8]
  const answer = [];
  let i = 0;
  let j = 0;

  while (i < arrA.length && j < arrB.length) { // 1)
    if (arrA[i] === arrB[j]) {
      answer.push(arrA[i]);
      i++;
      j++;
    } else if (arrA[i] < arrB[j]) {
      i++;
    } else {
      j++;
    }
  }

  return answer;
};

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

• 각 배열에 포인터를 만든다 i,j = 0
• a배열의 포인터 i 와 b배열의 포인터 j 를 이용해서 차례대로 값을 비교한다.
• 만약 같다면 arrA[i]를 answer에 추가하고, i와 j를 각각 1씩 증가시킨다.
• arrB[j]값이 arrA[i]보다 크다면 i를 증가시킨다.
• arrB[j]값이 arrA[i]보다 작다면 j를 증가시킨다.
• 1) 처음에 이 부분을 어떻게 처리해야할지 고민했다. 🧐
  while (i < arrA.length && j < arrB.length) {...} 이 조건은 배열 arrA와 arrB의 모든 원소를 비교하는 역할을 한다. 이 조건은 두 배열 중 하나라도 모든 원소를 확인했을 때 반복을 멈추게 된다. 😀

✍️ solution

function solution(arr1, arr2){
    let answer=[];
    arr1.sort();
    arr2.sort();
    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));