[ 자바스크립트(JavaScript) ] section05 - 2 - 공통 원소 구하기

📍 section05 - 2 - 공통 원소 구하기

A, B 두 개의 집합이 주어질 때 공통 원소를 추출하여 오름차순으로 출력하는 문제다. 투 포인터를 사용해야 하는 이유는 N의 크기가 30,000인데, 이를 O(N^2)으로 풀게 되면 최악의 경우 1초당 9억번의 연산을 해야 하기 때문에 시간 초과가 난다. 따라서, O(N^2) 보다 작은 시간 복잡도로 계산해야 한다. 만약, N의 범위가 30,000보다 더 작다면 O(N^2)으로 bruteForce로도 풀 수 있다.bruteForce의 장점은 모든 경우의 수를 검사하기 때문에 정확한 결괏값이 나온다는 점이다.

 

//O(N^2), bruteForce
let n = 5;
let arr1 = [1, 3, 9, 5, 2];

let m = 5;
let arr2 = [3, 2, 5, 7, 8];

console.log(solution(n, arr1, m, arr2));

function solution(n, arr1, m, arr2) {
  let ans = [];

  for (let i = 0; i < n; i++) {
    let target = arr1[i];
    for (let j = 0; j < m; j++) {
      if (target === arr2[j]) ans.push(target);
    }
  }

  ans.sort((a, b) => a - b);
  return ans;
}

 

728x90

 

하지만, 이번 섹션이 효율성을 고려하는 문제인 만큼 투 포인터로 풀어보자. 투 포인터를 사용하면 NlogN+N+M 즉, O(NlogN)에 풀 수 있는데, 시간 내에 들어올 수 있다. 풀이 방법은 다음과 같다.

 

1. 두 배열을 각각 sort(nlogn)한다.
2. 투 포인터 인덱스를 가리키는 p1, p2를 0으로 선언한다.
3. 만약, p2가 가리키는 값이 p1보다 크면 현재 p2 뒤로는 p1보다 같거나 작은 값이 없다. 왜냐하면 배열은 이미 오름차순으로 정렬되어있기 때문이다. 따라서 p1++을 해준다.
4. p1===p2이면 ans에 넣고 다음 숫자를 검사하기 위해 p1++, p2++ 해준다.
5. p1>p2인 상황이면 p2++를 해준다.
6. p1 혹은 p2가 n보다 커지면 반복문을 종료한다.(한쪽 탐색이 먼저 끝나면 다른 쪽은 탐색할 필요가 없기 때문이다.)

 

// O(NlogN + N + M), Two Pointer
let n = 5;
let arr1 = [1, 3, 9, 5, 2];

let m = 5;
let arr2 = [3, 2, 5, 7, 8];

console.log(solution(n, arr1, m, arr2));

function solution(n, arr1, m, arr2) {
  let ans = [];
  let p1 = (p2 = 0);
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);

  while (p1 < n && p2 < m) {
    if (arr1[p1] === arr2[p2]) {
      ans.push(arr1[p1++]);
      p2++;
    } else if (arr1[p1] < arr2[p2]) p1++;
    else p2++;
  }

  return ans;
}