[baekjoon] 백준 1043번 : 거짓말 (by python 파이썬) set 집합

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

1043번: 거짓말

 

정답 code

#거짓말
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
know = set(input().split()[1:])
party = []

for _ in range(m):
    party.append(set(input().split()[1:]))

#매 파티마다 진실을 알게되는 사람이 생김으로 파티 수만큼 반복
for _ in range(m):
    for p in party:
        if p & know:
            know = know.union(p) #union으로 합집합

cnt = 0
for p in party:
    if p & know:
        continue
    cnt += 1

print(cnt)

 

solution

거짓말을 알고있는 사람들을 know에 저장,

party에는 각 파티에 온사람들을 저장,

know와 party사이에 교집합이 존재한다면 그 파티에 온 사람들을 know에 합집합 시킨다.

 

몇가지 걸렸던 문제는 둘째줄 입력과 셋째줄 입력 부터 마지막 입력까지인데

둘째줄엔 진실을 아는 사람의 수와 번호를 입력으로 받는다.

여기서 진실을 아는 사람의 수가 0이면 뒤에 입력을 받지 않음으로 일반적으로 입력을 받으면 오류가 발생한다.

또한 셋째줄 부터는 파티에 오는 사람의 수와 번호인데 각 파티마다 오는 사람의 수가 다름으로 다르게 처리를 해주어야 한다.

 

이걸 해결하기 위한 방법이 [1:]로 [1]인덱스부터 입력을 받는 것이다.

진실을 아는 사람의 수와 파티에 오는 사람의 수는 사용 하지 않음으로 따로 저장을 하지 않는다.

 

이렇게해서 party에 저장후 각 파티에 온 사람을 p로 추출하여 know와 비교한다.

이때 매 파티마다 진실을 알게 되는사람이 생길 수 있음으로 파티 수(m) 만큼 반복해야한다.

만약 교집합이 존재한다면 union을 통해 know에 합집합 시킨다.

 

마지막으로 각 파티의 사람과 know에 합집된 사람들사이에 교집합이 없는 파티의 수를 카운트해 출력해주면 된다.