[c++] BOJ 18119 :: 단어 암기

문제

단어 암기 문제 바로가기

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

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

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

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

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

 

풀이

• 단어의 길이가 10^3이나 되므로 일일이 비교하기 힘듬
• bit 연산을 통해 비교할 수 있는 방안 생각
• 알파벳 26자리를 bitmap으로 나타낼 때
  • 2^26 < (2^3)^9 < 10^10 이므로 충분히 int 형으로 표현 가능

 

코드

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

using namespace std;

int N, M;
vector<int> words;
int remember;

// bit로 표현
// 26글자 => 2진수로 표현

int getWordNumber() {
    int count = 0;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == (words[i] & remember)) {
            count += 1;
        }
    }
    return count;
}

int getQueryResult(int func, int target) {
    int idx = target - 'a';
    if (func == 1) {
        // forget
        remember &= ~(1 << idx);
    }
    else {
        // remember
        remember |= (1 << idx);
    }
    return getWordNumber();
}

int main() {
    cin >> N >> M;
    remember = (1 << 27)-1;

    for (int i = 0; i < N; i++) {
        string str; cin >> str;
        int wordBit = 0;
        for (int j = 0; j < str.length(); j++) {
            int idx = str[j] - 'a';
            wordBit |= 1 << idx;
        }
        words.push_back(wordBit); // 비트 저장
    }

    for (int i = 0; i < M; i++) {
        int func; char target;
        cin >> func >> target;
        cout << getQueryResult(func, target) << '\n';
    }
}

 

결과

아이디	메모리	시간	코드 길이
gmldms784	2160	3436	955