거짓말 ( 1043번 )

1043번: 거짓말

 

나의 풀이

import sys

def _main(n_ct, p_ct, s_list, p_list):
    answer = 0

    for _ in range(p_ct):
        for now_pt in p_list:
            if (s_list & now_pt):
                s_list = (s_list | now_pt)
    for part in p_list:
        if (part & s_list):
            continue
        answer += 1

    return answer

n_ct, p_ct = map(int, sys.stdin.readline().rstrip().split())
s_list = set(list(map(int, sys.stdin.readline().rstrip().split()))[1:])
p_list = [set(list(map(int, sys.stdin.readline().rstrip().split()))[1:]) for _ in range(p_ct)]

print(_main(n_ct, p_ct, s_list, p_list))

 

시간 복잡도

for _ in range(p_ct) : 파티 수 만큼 순회 ( 선형 시간 복잡도 )
    for now_pt in p_list : 파티 집합 순회 ( 선형 시간 복잡도 )
    
해당 파이썬 알고리즘 시간복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )