18119 단어 암기

개인적으로 재밌는 문제였다. 내가 비트마스킹을 잘 몰랐기도 했지만 풀이시간이 오래걸렸다.

문제의 메커니즘은 비교적 간단했지만 비트열에서 1, 0으로 바꾸는 과정이 생소하여 더뎠었다.

고찰

이 문제에 비트마스킹으로 접근한 이유는 다음과 같다.

1. 전체 집합을 비트열로 나타낼 수 있다.
   • 알파벳은 26개이므로 32비트 정수의 비트열에서 다음과 같이 표현할 수 있다.
     0000 0011 1111 1111 1111 1111 1111 1111
     0000 00zy xwvu tsrq ponm lkji hgfe dcba
2. 선택지로 주어진 집합들을 비트열로 취급할 수 있다.
   
   • 예를 들어 apple은 문제의 조건에서 중복을 고려하지 않기 때문에 {a, p, l, e}로 생각해볼 수 있고, 각각의 알파벳에 해당하는 비트들을 1로, 그 외의 비트들은 0으로 마스킹한 합으로 단어를 표현할 수 있다.
3. 입력이 단순하다.
   • 특정 알파벳을 잊어버리거나, 기억이 나는건 특정 비트열을 0 또는 1로 하는 것과 같다.
     즉, 저장하고 있는 비트열에서 입력으로 들어온 비트열을 처리하고 단어 (특정 비트열)와 비교하면 표현여부를 알 수 있다.

1, 2번은 고려했지만 3번은 고려하지 못하여 다소 지저분한 코드로 해결했다. 주어진 조건들을 어떻게 표현할 수 있을지 고민해보는게 필요한 것 같다.

정답 코드 (수정이 필요함)

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define BIT_MASK 0x7fffffff
int N, M;
int substi(const string& str)
{
	int num = 0;
	for (const auto& item : str) {
		num |= BIT_MASK & (1 << item - 'a');
	}
	return num;
}
void oper(int idx, char c, vector<int>& v, const vector<int>& org)
{
	int len = v.size();
	for (int i = 0; i < len; i++) {
		if (idx == 1) {
			v[i] = v[i] & ~(1 << c - 'a');
		}
		else {
			v[i] |= org[i] & (1 << c - 'a');
		}
	}
}
int main()
{
	string s;
	cin >> N >> M;
	vector<int> v(N, 0);
	vector<int> org(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> s;
		v[i] = substi(s);
	}
	org = v;
	int op, cnt = 0;
	char c;
	for (int i = 0; i < M; i++) {
		cin >> op >> c;
		oper(op, c, v, org);
		for (int j = 0; j < org.size(); j++) {
			if (v[j] == org[j]) {
				++cnt;
			}
		}
		printf("%d\n", cnt);
		cnt = 0;
	}
	return 0;
}