BOJ 18119 단어 암기

출처 : https://www.acmicpc.net/problem/18119

첫번 째 생각 :
완전 나이브
O(단어 개수 * 단어길이 * 쿼리 개수)

이러면 왠지 메모리에서 크트 당할꺼 같아서 좀 더 생각 해봄

두번 째 생각 :
어떤 알파벳에 대해서 내가 알고있다, 모르고 있다만 알고 있으면 대니깐
각 단어에 대해서 알파벳에 대해서 1(알고있다), 0(모르고 있다) 이렇게 표시를 하면됨 (char 배열)
이러면 왠지모르게 tle는 면할 수 있을것 같았음 (복잡도는 아니라고 외지치만 n = 1000인 플로이드 와샬도 통과를 하듯이?)

는 tle였구연

세번 째 생각 :
비트를 사용
두번 째 생각에서 1 혹은 0으로 표현하고 알파벳도 26개 바께 없으니 비트를 쓰면 됨
그리고 내가 해당 단어를 아냐 모르냐는 & 연산자를 사용하면 되겠다 싶었음

아근데 이래도 빅오표기법 좀 그런데 그래도 신뢰의 제출이란게 있지 않겠음??

(word & state) == word

이러면 단어를 알고 있는것이 됨.

아래는 내 코드

#include<stdio.h>
int cur = 0xffffffff, n, table[10000];
int count();
void make_answer();
int main(void)
{
	make_answer();
	return 0;
}
void make_answer()
{
	int qn, i, k, j, q, ans;
	char buf[10001];
	scanf("%d %d", &n, &qn);
	for (i = 0; i < n; i++)
	{
		scanf("%s", buf);
		for (j = 0; buf[j]; j++)
		{
			table[i] |= 1 << (buf[j] - 'a');
		}
	}
	while (qn--)
	{
		scanf("%d", &q);
		scanf("%s", buf);
		if (q == 1)
		{
			cur &= ~(1 << (buf[0] - 'a'));
		}
		else
		{
			cur |= (1 << (buf[0] - 'a'));
		}
		ans = count();
		printf("%d\n", ans);
	}
}
int count()
{
	int i, cnt;
	for (i = cnt = 0; i < n; i++)
	{
		if ((table[i] & cur) == table[i])
		{
			cnt++;
		}
	}
	return cnt;
}