백준 1269번 풀이

문제

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

1269번: 대칭 차집합

두 집합의 차집합들의 길이 합을 출력해보자

 

풀이

이거 풀이가 투트랙인데 둘 다 맞긴 맞았다.

 

import sys

N, M = map(int, sys.stdin.readline().split())

set_x = set(map(int,sys.stdin.readline().split()))
set_y = set(map(int,sys.stdin.readline().split()))

일단 기본 골자인 입력 받아서 집합 만드는 건 같다. 대신 입력이 한 줄에 공백으로 나누어져 있기 때문에 map을 쓸 것이다. 그 왜 가끔 풀이에 리스트(맵(뭐시기)) 있는 그런거 말하는거다. 여기서는 리스트 말고 셋.

 

첫번째 풀이

x_y = set_x - set_y # X-Y
y_x = set_y - set_x # Y-X

일단 집합 X와 집합 Y가 있을 때, 두 집합의 차집합은 뭐에서 뭘 빼느냐에 따라 다르다. X에서 Y 뺀거랑 Y에서 X 뺀거랑은 다른거다. 즉, 차집합에 교환법칙따원 성립하지 않는다. 그니까 정직하게 쌍방 빼서 차집합을 구하면 된다.

 

import sys

N, M = map(int, sys.stdin.readline().split())

set_x = set(map(int,sys.stdin.readline().split()))
set_y = set(map(int,sys.stdin.readline().split()))

x_y = set_x - set_y # X-Y
y_x = set_y - set_x # Y-X

symmetry_cha = len(x_y) + len(y_x)

print(symmetry_cha)

그리고 차집합 길이 두개 더해서 정직하게 출력하면 된다. 끝.

 

두번째 풀이

import sys

N, M = map(int, sys.stdin.readline().split())

set_x = set(map(int,sys.stdin.readline().split()))
set_y = set(map(int,sys.stdin.readline().split()))

union_xy = set_x | set_y
intersection_xy = set_x & set_y

print(len(union_xy - intersection_xy))

벤 다이어그램 있으면 이해하기 쉬운데...

 

여기 두 집합이 있으면 이 문제에서 구해야 하는 부분이

 

여기 빨간색으로 칠한 부분이다. 그리고 

 

분홍색이 합집합이고 보라색이 교집합이다.

 

그리고 초록색 선이 우리가 문제에서 구할 부분이니까 합-교하면 되잖음.

 

둘 다 제출해서 맞긴 맞았는데, 두번째 풀이는 메모리 사용량이랑 소요시간이 첫번째 풀이에 비해 조금 더 길다. (아래가 첫번째 풀이, 위에가 두번째 풀이) 그니까 코드 길이는 두번째 풀이가 좀 더 간소하지만, 메모리 사용량이나 소요시간을 놓고 본다면 첫번째 풀이가 좀 더 효율적이라고 할 수 있다.