[Baekjoon]1822번 차집합 - Javascript

https://www.acmicpc.net/problem/1822

1822번: 차집합

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

예제 입력 1 복사

4 3
2 5 11 7
9 7 4

예제 출력 1 복사

3
2 5 11

예제 입력 2 복사

3 5
2 5 4
1 2 3 4 5

예제 출력 2 복사

0

 

문제풀이(1)

A 집합에는 속하지만 B 집합에는 속하지 않는 A 집합의 값을 찾는 문제이다.
두가지 풀이방법을 생각할 수 있다.
1. set 객체를 활용해서 집합 B를 set 객체에 할당한뒤 집합 A를 순회하며 집합 B에 존재 유무를 판단하면 된다.
2. 2진 탐색을 활용하여 집합 B에 집합 A의 값이 존재 유무를 판단하면 된다.
2진 탐색은 O(log N)의 시간복잡도를 갖지만 
set 객체를 활용한 풀이은 O(N)의 시간복잡도를 가지게 되어 이럴경우는 2진탐색보다 set 객체를 활용한 풀이가 더 좋다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

input.shift();

const arrA = input[0].split(" ").map(Number);
const arrB = new Set(input[1].split(" ").map(Number));

const answer = [];

arrA.forEach((num) => {
  if (!arrB.has(num)) {
    answer.push(num);
  }
});

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

console.log(answer.length === 0 ? 0 : `${answer.length}\n${answer.join(" ")}`);

 

문제풀이(2) - 2진탐색 풀이

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

input.shift();

const arrA = input[0].split(" ").map(Number);
const arrB = input[1]
  .split(" ")
  .sort((a, b) => a - b)
  .map(Number);

const answer = [];

const binarySearch = (arr, target) => {
  let low = 0;
  let high = arr.length - 1;
  let result = false;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (arr[mid] < target) {
      low = mid + 1;
    } else if (arr[mid] > target) {
      high = mid - 1;
    } else {
      result = true;
      break;
    }
  }
  return result;
};

arrA.forEach((num) => {
  if (!binarySearch(arrB, num)) {
    answer.push(num);
  }
});

console.log(answer.length === 0 ? 0 : `${answer.length}\n${answer.join(" ")}`);