취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18119번 문제인 단어 암기이다.
문제는 아래 링크를 확인하자.

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

알고 있는 문자의 집합이 바뀔 때마다 모든 단어를 구성하는 문자를 하나하나 확인하는 것은 매우 비효율적이다. 이를 어떻게 효율적으로 바꿀 수 있을까?

먼저, 어떤 단어를 알기 위해서는 그 단어를 구성하는 어떤 문자가 1회 사용되어도 다회 사용되어도 그 문자를 알고 있어야 한다는 사실을 관찰하자. 따라서 각 단어를 알고 있는지의 여부를 확인하기 위해 해당 문자를 구성하는 문자의 집합만을 관리해도 문제가 없음을 알 수 있다. 알파벳 소문자는 26가지뿐이므로, 각 집합의 원소는 많아야 26개가 될 것이다.

여기에서 더 나아가 해당 집합은 i번째 알파벳이 존재할 경우 i번째 비트가 1, 그렇지 않을 경우 i번째 비트가 0인 크기 26의 비트셋으로 나타낼 수 있음을 관찰하자.

이를 이용하면 각 단어를 알고 있는지를 확인하는 것은 bitwise and 연산을 이용해 매우 빠르게 진행할 수 있게 된다. 이 점을 이용해 문제를 해결하자.

\(NM\)의 상한은 5억이고 제한시간이 4초임을 확인하자. 또한 4초에 5억회의 비트연산은 충분히 실행할 수 있음을 상기하자. 실제로 글쓴이의 코드는 1초 미만으로 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int N, M;
int A[10000];
int mm = 67108863;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int &x = A[i];
		string s; cin >> s;
		for (auto &l : s) x |= (1 << (l - 'a'));
	}

	while (M--) {
		int ans = 0;
		char c; cin >> c >> c;
		mm ^= (1 << (c - 'a'));
		for (int i = 0; i < N; i++) {
			if ((A[i] & mm) == A[i]) ans++;
		}
		cout << ans << '\n';
	}
}