18119번: 단어 암기

문제 설명

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

18119번: 단어 암기

 

[문제]

 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다.

 다음과 같은 쿼리들이 주어진다.

• 1 x : 알파벳 x를 잊는다.
• 2 x : 알파벳 x를 기억해 낸다.

 처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다.

 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.

 

[입력]

 첫 번째 줄에는 정수 N (1 ≤ N ≤ 104)과 M (1 ≤ M ≤ 5×104)이 주어진다.

 다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 103을 넘지 않는다.

 다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x는 알파벳 소문자이다.

 o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.

 

[출력]

 각 쿼리마다 정수 하나를 출력한다.

 

[예제 입력 1]

5 10
apple
actual
banana
brick
courts
1 l
1 b
1 c
1 n
2 l
2 b
1 s
2 c
2 s
2 n

[예제 출력 1]

3
1
0
0
1
1
1
3
4
5

---

풀이

 문제의 해결을 위해선 현재 알고있는 알파벳들과 단어에 포함되어 있는 알파벳을 비교할 수 있어야 한다. 그런데 단순히 단어 속 알파벳을 일일히 비교하면 시간이 오래걸리기 때문에, 이를 빠르게 비교하기 위해선 비트 연산을 사용해야 한다.

 우선 단어들을 입력받아 해당 단어 속 알파벳들을 대표하는 비트로 변환하여 저장을 해놓는다. 이후 현재 알고 있는 알파벳들을 대표하는 비트를 만든 후, 쿼리를 통해 해당 알파벳에 해당하는 비트 위치를 1이나 0으로 변환한다. 이후에는 현재 알고 있는 비트와 단어 비트를 비교하는데, 쉽게 비교를 하기 위해선 알고 있는 비트를 not(~) 연산을 통해 뒤집어 단어 비트와 AND 연산을 진행하면 된다. 만약 모르는 알파벳들로만 이루어져 있는 비트 변수에 단어 비트와 AND 연산을 했을 때 결과 값이 0이면 모르는 알파벳이 현재 단어에선 존재하지 않는다는 결과기 때문에, 이 때 단어 카운트를 1 증가시켜 주면 된다.

 추가적으로 쿼리에서는 앞의 숫자 1과 2를 통해 잊는 것과 기억하는 것을 구분하지만, 입력 조건 시 잊을 때는 해당 알파벳을 기억하고 있었음이 보장되고, 기억할 때는 잊고 있었음이 보장되기 때문에 쿼리 구분없이 xor 연산을 반복하면 된다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> wordsBits;//비트 변환된 단어들의 배열

int know(int status) {//완전히 알고 있는 단어 개수 계산
	int count = 0, unknownBit = ~status;

	for (int i = 0; i < wordsBits.size(); i++)
		if ((wordsBits[i] & unknownBit) == 0)
			++count;
	
	return count;
}

int main() {
	int N, M, status = 0;
	string s;
	vector<int> result;

	status = (1 << 32) - 1; //모든 알파벳을 기억하는 상태

	cin >> N >> M;

	for (int i = 0; i < N; i++) { //단어 입력받아 비트 변환 처리
		int wordBits = 0;
		cin >> s;

		for (int j = 0; j < s.size(); j++)
			wordBits |= 1 << (s[j] - 'a');

		wordsBits.push_back(wordBits);
	}

	for (int i = 0; i < M; i++) { //쿼리 입력 받아 처리
		int num, bit = 0;
		char alphabet;
		cin >> num >> alphabet;

		if(alphabet!='a'&& alphabet != 'e'&& alphabet != 'i'&& alphabet != 'o'&& alphabet != 'u')
			bit = 1 << (alphabet - 'a');

		status ^= bit; //상태에 알파벳 처리

		result.push_back(know(status));
	}

	for (int i = 0; i < M; i++)
		cout << result[i] << "\n";

	return 0;
}

---

결과