BOJ18119 단어 암기 /C++

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

18119번: 단어 암기

백준 18119 단어암기 문제입니다.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

vector<int> words;

int convertWordsToBit(string s) {
	int bit = 0;
	for (auto c : s) 
		bit |= (1 << (c - 'a'));
	return bit;
}

void solution() {
	int n, m;
	string s;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		words.push_back(convertWordsToBit(s));
	}
	int o;
	char x;
	int bit = 0;
	for (int i = 0; i < 26; i++) {
		bit |= (1 << i);
	}
	for (int i = 0; i < m; i++) {
		int cnt = 0;
		cin >> o >> x;

		if (o == 1)
			bit &= ~(1 << x - 'a');
		else
			bit |= (1 << x - 'a');
		for (auto s : words) {
			if ((s & bit) == s)
				cnt++;
		}
		cout << cnt << "\n";
	}
}

int main(void) {
	solution();
}

아이디어

문제는 직관적으로 풀이하면 되기때문에 어려운것은 없지만 이런 문제들은 시간초과에 주의해야 함

단어 확인을 할때 string을 하나씩 확인하면 시간복잡도가 1000x10000x10000 인데,

비트마스킹을 사용하면 1000x10000이다.