[BOJ_14569] 시간표 짜기(python)

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

문제

---

코드 1 - subset

cls = []
n = int(input())
for i in range(n):
    a = list(map(int, input().split()))
    cls.append(set(a[1:]))
 
m = int(input())
for _ in range(m):
    b = list(map(int, input().split()))
    q = set(b[1:])
    cnt = 0
    for i in cls:
        if i.issubset(q):
            cnt += 1
    print(cnt)

Idea 1

a.issubset(b) = a 가 b의 하위 집합인가를 판단 

---

코드 2 - bitmask

cls = []
n = int(input())
for i in range(n):
    r = 0
    a = list(map(int, input().split()))
    for i in a[1:]:
        r |= (1 << i)
    cls.append(r)

m = int(input())
for _ in range(m):
    s = 0
    b = list(map(int, input().split()))
    for i in b[1:]:
        s |= (1 << i)
    cnt = sum(1 for i in cls if (s & i) == i)
    print(cnt)

Idea 2

하나씩 저장
r = 000000
r |= (i << 1) : 000001
r |= (i << 2) : 000011

포함 여부 확인
(s & i) == i
s = 010011
r = 000011
(010011 & 000011) == 000011