boj 1043 거짓말(골드4)
문제
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))
교집합 합집합 하려는 두 배열의 길이만큼 쓰인다
간단하게 &, | 기호로 사용 가능하다
결과
끝!
Author And Source
이 문제에 관하여(boj 1043 거짓말(골드4)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kjo1130/boj-1043-거짓말골드4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)