백준 18119 - 단어 암기

백준 18119 문제 바로가기

풀이

1<=N<=10^4개의 문자열이 주어지고, 1<=M<=5*10^4개의 쿼리가 주어진다. (문자열의 길이는 10^3 이하이다.)

M개의 줄에는 정수 o와 문자 x가 하나씩 주어지는데, o = {1, 2} 중 하나이고, x는 알파벳 소문자이다.

o가 1이면 x를 잊는다는 뜻이고, o가 2이면 x를 기억해낸다는 뜻일 때 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하면 된다.

---

우선은 10000개의 문자열과 50000개의 쿼리가 주어졌을 때 모든 문자열 길이에 대해 알 수 있는 단어인지 일일이 확인하는 작업은 시간 초과를 유발하므로 전처리를 하여 시간을 줄일 수 있는 다른 방법을 찾아야 한다.

문제 조건에 소문자 알파벳만 주어진다고 했으므로 각 문자열을 비트 집합으로 표현할 수 있으며, N개의 문자열 전체를 알기 위해 필요한 알파벳 26개의 공간을 int 자료형의 비트 상태로 표현할 수 있다. (예를 들어 abc라는 단어를 알고 있다면 111(2), d라는 단어를 알고 있다면 1000(2)와 같이 이진수로 생각하는 것이다.)

1. N개의 문자열에 포함된 모든 알파벳은 기억하고 있는 상태여야 하므로 int bitSet과 같은 변수에 상태를 기억시킨다. 각각의 문자열에 대해서도 비트 집합을 생성한다.
2. 이후 M개의 쿼리에 대해서 o가 정수 1이면 알파벳 x를 잊기 위해 AND연산과 비트 반전 연산(~)을 사용하여 해당 알파벳 위치의 비트를 0으로 만들고, o가 정수 2이면 알파벳 x를 기억하기 위해 OR연산을 사용하여 해당 알파벳 위치의 비트를 1로 만든다.
3. 특정 문자열이 갖는 비트 집합(useAlphaBit[j])과 현재 기억하고 있는 비트 집합(int bitset)을 AND(&)연산하여, 그 결과가 useAlphaBit[j]이면 단어를 알고 있는 것이다.

위 과정을 코드로 나타내면 아래와 같다.

소스 코드

필요한 내용이 위에 다 적혀있어서, 핵심이 되는 부분만 간략하게 첨부한다.

// 문자열을 입력받을 때 전처리
for (int i = 0; i < N; ++i) {
    scanf("%s", str);
    for (int s = 0; str[s] != '\0'; ++s) {
        int num = str[s] - 'a';
        useAlphaBit[i] |= (1 << num);
        bitSet |= (1 << num);
    }
}

// 쿼리 처리
for (int i = 0; i < M; ++i) {
    scanf("%d %c", &o, &x);
    int num = x - 'a';
    if (o == 1) {
        bitSet &= ~(1 << num);
    }
    else {
        bitSet |= 1 << num;
    }

    int cnt = 0;
    for (int j = 0; j < N; ++j) {
        if ((useAlphaBit[j] & bitSet) == useAlphaBit[j])
            ++cnt;
    }
    printf("%d\n", cnt);
}

후기

문제 아이디어가 참 괜찮다는 생각이 들었고, (C++기준)맞은 사람을 보면 시간이 120ms 이내로 드는 빠른 코드가 존재하기 때문에 좀 더 최적화 할 수 있나보다.