BOJ 19585. 전설

문제링크 

 

이 문제는 solved.ac Class 6++을 따기 위해 푼 문제였는데, 상당히 나를 귀찮게 했다. 그리고 맞고도 무언가 찝찝해 나와 같은 어려움을 겪고 있는 분들께 도움이 되고자 풀이를 작성해본다.

 

Problem

$C(1\leq C \leq 4000)$개의 색깔을 나타내는 문자열과 $N(1\leq N \leq 4000)$개의 닉네임을 나타내는 문자열이 주어져있다. 

이때 $Q(1 \leq Q \leq 20000)$개의 문자열에 대해 해당 문자열이 색깔 문자열 + 닉네임 문자열 꼴인지 판별하는 문제이다.

색깔, 닉네임 문자열의 길이 : 1000 이하, 판별 문자열의 길이: 2000 이하

Discussion

문제를 읽고 처음 든 생각은 "참 제한이 애매하다"였다. 제한시간이 3초이긴 하지만 어떤 풀이를 가져와도 시간이 부족할 거 같았다. 그렇게 고민을 거듭했는데 그래도 그나마 Rabin-Karp가 될 것 같아서 구현하기로 했다.

Solution

우선, Rabin-Karp Algorithm을 모른다면 여기를 보고 오자. 간단히 말해서 문자열을 Hashing 해서 일치 판별을 $O(1)$에 하는 기법인데, 운이 없으면 Hash Collision이 날 수 있기 때문에 잘 사용해야 한다. 일단 될 것이라고 믿고 색깔 문자열, 닉네임 문자열을 모두 Hash 해서 Vector에 저장해놓는다 (총 $C+N$개). 그리고 $Q$개의 문자열에 대해, 색깔 문자열과 닉네임 문자열의 경계가 될 수 있는 부분을 모두 보면서 앞부분의 Hash값과 뒷부분의 Hash값이 모두 일치하는지 확인한다. 모두 일치하면 Yes이고, 모든 가능성에 대해 Yes가 아니라면 No라고 할 수 있다. 이때 Hash값이 일치하는지는 정렬된 Vector에서 Binary Search를 했다. 구현도 그다지 어려운 부분이 없다.

 

시간 복잡도: $O((C + N)L + QL(\log_2 C + \log_2 N))$ ($L$: 문자열의 길이 $=2000$)

 

그런데 문제는 지금부터였다. 고질적인 Rabin-Karp의 문제가 터졌다. 처음 여러 번을 WA를 받았는데 그것은 Hash Function을 구성할 때 'a'를 1이 아닌 0으로 해서 발생한 문제였으나, 그것을 고친 뒤에도 WA를 받았다. 이는 Hash Collision이 발생한다는 말이었고, 소수를 조금씩 바꿔가면서 몇 번 시도했지만 바뀐 것은 없었다. 그래서 Hash Function을 2개로 만들었다. 이 방법은 거의 무조건 성공한다고 할 수 있다. 그런데 이번에는 TLE가 났다. 정말 난처한 상황이었다. 그래서 이 방법은 과감히 포기하고 Hash Function 1개로 다시 돌아왔는데, 소수 조합을 바꿀 때마다 WA혹은 TLE가 났다.

 

그래서 한 가지 꾀를 부렸다. 색깔 문자열을 매칭 시킬 때 맨 앞 알파벳이 다르다면 뒤의 문자열은 볼 필요도 없기에 색깔 문자열들을 저장시킬 때 앞 알파벳에 따라 26개의 Vector에 나눠서 저장했다. 닉네임 문자열도 마찬가지로 맨 뒤 알파벳을 기준으로 나눠 저장했다. 이 방법을 쓰니 시간은 확실히 조금 준 것 같았고, Hash값의 codomain을 2배 정도 키워(mod값을 2배로 키워줌) 시도했더니 놀랍게도 3초 제한에 2992ms로 AC를 받을 수 있었다. 정말 이렇게 까지 해야 하나 싶어 AC를 받은 사람들의 코멘트를 몇 개 읽어보니 시간을 보다 효율적으로 줄일 수 있는 방법이 있었다. 생각보다 간단한데, 나는 여태껏 색깔 문자열의 길이가 최대 1000인데도, 판별하려고 하는 문자열의 길이만큼 모두 탐색하고 있었다. 판별하려고 하는 문자열의 길이는 최대 2000이기에 굉장히 비효율적이었고, 시간을 반 정도로 줄일 수 있었다. 그래서 고치고 다시 제출해보니 1620ms로 AC를 받을 수 있었다. 여러모로 쉽지 않은 문제였다. 아래는 내 제출 흔적과 코드이다.

 

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back 
#define allv(V) (V).begin(), (V).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> base;

const int inf = INT_MAX;
const ll infll = LONG_LONG_MAX;
const ll mod = 2000000203LL;
const ll p = 1223LL;

int gcd(int x, int y){return y ? gcd(y, x % y) : x;}

ll c, n, q, ex[2020] = {1}, exr[2020] = {1};

string s;

ll hashh()
{
    ll ret = 0;
    for(int i = 0; i < s.size(); i++) ret = (ret + ex[i] * (s[i] - '_')) % mod;
    return ret;
}

ll f(ll x, ll y)
{
    ll ret = 1;
    ll t = x;
    for(ll i = 1; i <= y; i <<= 1)
    {
        if(y & i) ret = ret * t % mod;
        t = t * t % mod;
    }
    return ret;
}

vector<ll> vc[26], vn[26];

bool chk()
{
    ll h = hashh();
    ll tmp = 0;
    int idx1 = s[0] - 'a';
    int idx2 = s[s.size() - 1] - 'a';
    for(int i = 0; i < min(1000, (int)s.size() - 1); i++)
    {
        tmp = (tmp + ex[i] * (s[i] - '_')) % mod;
        ll tmp2 = (h - tmp + mod) * exr[i + 1] % mod;
        if(!vc[idx1].empty() && tmp <= vc[idx1].back() && *lower_bound(allv(vc[idx1]), tmp) == tmp && 
            !vn[idx2].empty() && tmp2 <= vn[idx2].back() && *lower_bound(allv(vn[idx2]), tmp2) == tmp2) return true;
    }
    return false;
}

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

    for(int i = 1; i < 2020; i++)
    {
        ex[i] = ex[i - 1] * p % mod;
        exr[i] = f(ex[i], mod - 2);
    }

    cin >> c >> n;
    for(int i = 0; i < c; i++)
    {
        cin >> s;
        vc[s[0] - 'a'].pb(hashh());
    }
    for(int i = 0; i < n; i++)
    {
        cin >> s;
        vn[s[s.size() - 1] - 'a'].pb(hashh());
    }
    
    for(int i = 0; i < 26; i++)
    {
        sort(allv(vc[i]));
        sort(allv(vn[i]));
    }

    cin >> q;
    for(int i = 0; i < q; i++)
    {
        cin >> s;
        cout << (chk() ? "Yes\n" : "No\n");
    }
    return 0;
}