[BOJ] 1269 - 대칭 차집합

문제

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

1269번: 대칭 차집합

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 두 집합 A와 B에 대해 (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 할 때, 그 원소의 개수를 구하여라.

 

예시 )

$$ A = \{1, 2, 4 \}, B = \{2, 3, 4, 5, 6 \}$$

$$ A-B = \{1 \}$$

$$ B-A = \{ 3, 5, 6\}$$

$$ A \triangle B=(A-B)\cup(B-A) = \{1, 3, 5, 6\} $$

 

입력으로 첫 번째 줄에 A와 B의 원소의 개수, 두 번째 줄에 A의 원소, 세 번째 줄에 B의 원소를 받는다.

 

풀이

틀린 풀이 - 시간 초과

리스트 컴프리헨션을 이용해 a의 원소 중 b에는 없는 원소의 리스트, b의 원소 중 a에는 없는 원소의 리스트의 구하여 그 길이의 합을 출력한다.

리스트를 전부 순회해야 해서 그런지 시간 초과가 발생했다.

import sys

ac, bc = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
print(len([i for i in a if i not in b]) + len([i for i in b if i not in a]))

 

맞은 풀이 - 집합의 성질 이용

집합의 성질을 이용하면 여러 가지 방법으로 대칭 차집합을 구할 수 있다. 이 문제의 경우에는 아래의 방법이 가장 간단한 방법인 것 같다.

$$ A \triangle B=(A-B)\cup(B-A) =  (A\cup B-B) +(A\cup B-A) $$

 

그림으로 표현하면 아래와 같다.

 

따라서 각 집합의 길이와 두 집합의 합집합의 길이를 이용하면 대칭 차집합의 원소의 개수를 계산할 수 있다.

import sys

sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
print(2 * len(set(a + b)) - len(a) - len(b))

 

맞은 풀이 - set 연산 이용

Python의 set 데이터형은 집합 연산을 수행할 수 있다. 

대칭차집합의 경우 연산자 ^ 또는 symmetric_difference 함수를 이용하여 구할 수 있다.

 

^ 연산

import sys

ac, bc = map(int, sys.stdin.readline().split())
a = set(map(int, sys.stdin.readline().split()))
b = set(map(int, sys.stdin.readline().split()))
print(len(a ^ b))

 

symmetric_difference

import sys

ac, bc = map(int, sys.stdin.readline().split())
a = set(map(int, sys.stdin.readline().split()))
b = set(map(int, sys.stdin.readline().split()))
print(len(a.symmetric_difference(b)))