[바미] 대칭 차집합

문제

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 번째 줄에서 집합 A와 B의 원소 개수 추출
const [sizeA, sizeB] = input[0].split(' ').map(Number);

// 집합 A와 B 생성
const setA = new Set(input[1].split(' ').map(Number));
const setB = new Set(input[2].split(' ').map(Number));

// 대칭 차집합 계산
const onlyA = Array.from(setA).filter(x => !setB.has(x));
const onlyB = Array.from(setB).filter(x => !setA.has(x));

// 결과 출력
console.log(onlyA.length + onlyB.length);

코드 설명

집합 A와 B의 원소 개수를 읽고, Set을 사용하여 집합 A, B를 생성해 줍니다.

그 후 아래의 코드에서

// 대칭 차집합 계산
const onlyA = Array.from(setA).filter(x => !setB.has(x));
const onlyB = Array.from(setB).filter(x => !setA.has(x));

대칭 차집합을 계산하는데 onlyA에서는 집합 A에서 B에 없는 원소를 찾고, onlyB에서는 집합 B에서 A에 없는 원소를 찾아준 뒤

onlyA와 onlyB의 길이를 더하여 대칭 차집합의 원소 개수를 출력해줍니다.

문제 해설

대칭 차집합은 두 집합 간의 차집합 연산을 통해 생성된 새로운 집합을 의미합니다.
두 집합 A와 B가 있을 때, 다음 두 가지 차집합을 합친 것인데 다시 말해, 두 집합에 모두 포함되지 않는 원소들의 모임입니다.

 

이 문제는 두 집합 A와 B에 대한 대칭 차집합의 원소 개수를 찾는 문제입니다. 대칭 차집합이 무엇인지만 알면 쉽게 풀 수 있는 문제입니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다.

 

두 집합 sizeA와 sizeB의 원소를 Set에 추가할 때 O(1)의 시간이 소요되므로 두 집합의 원소를 추가하는 데 걸리는 시간은 O(sizeA + sizeB)가 됩니다.

 

그리고 각 집합의 원소에 대해 상대 집합에 존재하는 지 확인하는 정에서 각 원소당 O(1)의 시간이 걸리게 됩니다.

이 과정에서 두 집합의 모든 원소를 한 번씩만 검사하기 때문에 O(sizeA + sizeB)의 시간이 필요하기 때문에

 

최종적인 시간 복잡도는 O(sizeA + sizeB)만큼 소요됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

두 집합 sizeA와 sizeB를 Set에 저장하기 위한 공간이 팔요한데 Set은 각 원소의 고유 값을 저장하고, sizeA와 sizeB 집합의 모든 원소를 저장하기 때문에 O(sizeA + sizeB)의 공간이 필요하게 됩니다.

 

그리고 대칭 차집합을 계산할 때 두 집합에 동시에 속하지 않는 모든 원소들을 저장하기 위한 배열을 사용하게 되고, 이 배열은 대칭 차집합의 원소 개수만큼의 공간을 필요로 하는데 최대 O(sizeA + sizeB)에가 차지하기 때문에

 

최종적인 공간 복잡도는 O(sizeA + sizeB)가 됩니다.