boj 1043 거짓말(골드4)

문제

boj 1043 거짓말

set을 사용해서 풀었다
파티의 참석 순서가 달라져도 같은 결과를 출력해야 한다는점을 빼먹으면 안된다!

O(n^2) 으로 돌리면서 중복체크했다
인풋이 50이하로 워낙 작아서 충분히 여유있을것이다

내 풀이

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

arr = list(map(int,input().split()))
del arr[0]
arr = set(arr)

party_list = []


for _ in range(m):
  k = list(map(int,input().split()))
  del k[0]
  k = set(k)
  party_list.append(k)

for _ in range(m):
  for i in range(m):
    k = party_list[i]
    if len(arr & k) > 0 :
      arr = arr | k


answer = 0
for party in party_list:
  if len(party & arr) == 0 :
    answer += 1

print(answer)

공부한것

set 교집합, 합집합

자주 쓰는 문법이 아니다보니깐 자꾸 까먹는다

교집합 : &
합집합 : |

둘다 시간복잡도는 O(len(arr1)) + O(len(arr2))
교집합 합집합 하려는 두 배열의 길이만큼 쓰인다

간단하게 &, | 기호로 사용 가능하다

결과

끝!