[백준] BOJ 3997 : 하이퍼드롬

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

3997번: 하이퍼드롬

문제를 읽어보면 조건들은 아래와 같습니다.

 

1. 대소문자 알파벳으로 이루어진 문자열이 주어짐

2. 문자열의 알파벳들을 적절히 바꿔서 팰린드롬을 만들 수 있다면 하이퍼드롬이라고 함

3. 그러면 문자열이 주어졌을 때, 연속된 부분 문자열들 중에서 하이퍼드롬인 개수를 물어봄

 

일단 이 문제와 N의 범위를 보고 저는 먼저 문제 및 하이퍼드롬의 특징을 먼저 알아보는게 필요하다고 생각이 들었습니다. 제가 파악한 특징들은 아래와 같습니다.

 

1. 일단 부분 문자열의 알파벳 위치들을 재배치 할 수 있습니다. 그렇다면 동일한 알파벳이 나오면 앞뒤로 배치하면 되므로 부분 문자열의 알파벳 개수들을 세어 보았을 때 전부 짝수라면 하이퍼드롬이라고 판단할 수 있습니다.

2. 다만, 문자열의 길이가 홀수라면 알파벳 하나는 홀수로 남고 나머지는 전부 짝수개로 남으면 하이퍼드롬입니다. 홀수 개인 알파벳을 정중앙에 위치시키면 됩니다.

 

그렇다면, 특정 위치에서 짝수 거리만큼 떨어진 곳에서까지의 총 알파벳 개수가 짝수이거나, 아니면 홀수 거리만큼 떨어진 곳에서까지의 총 알파벳 개수가 하나 제외하고 짝수라면 특정 위치부터 그 곳까지의 부분 문자열이 하이퍼드롬이 됩니다. 그러면 이걸 어떻게 쉽게 판별할 수 있을까요?

 

일단, 우리가 알파벳 개수를 꼭 알 필요가 있을까요? 어차피 홀수개인지 짝수개인지만 알면 됩니다. 그렇다면 짝수면 0, 홀수면 1로 표현이 가능합니다. 그리고 나올 수 있는 알파벳 개수는 소문자 26개, 대문자 26개로 총 52개입니다. 그래서 만약에 64-bit 정수형을 사용한다면 비트가 64개로 1 ~ 52번째 비트를 각 알파벳의 개수가 홀수개가 있는지, 짝수개가 있는지를 표현할 수 있습니다. 또한, XOR prefix sum을 활용한다면 \(s_i, \cdots, s_j\)내의 각 알파벳의 개수가 홀수개가 있는지 짝수개가 있는지도 쉽게 표현이 가능합니다.

 

여기까지가 아마 공통된 아이디어이고 이를 활용하여 구현하면 됩니다만, 구현 방법은 사람마다 좀 상이할 수 있어보여 제가 구현한 방식을 서술하겠습니다. (꼭 제가 구현한 방법이 아니더라도 다른 방법으로도 가능해보입니다.)

 

저는 일단 거리가 짝수만큼 떨어질 때와 홀수만큼 떨어질 때에 구해야 할 XOR 값이 다름에 주목해서, 홀수 번째에 받는 값이랑 짝수 번째에 받는 값을 map 두 개에 분리하여 저장하였습니다. (이를 각각 m1, m2라고 합시다.) map의 key로는 현재까지 prefix sum을 한 값을 넣었고, value로는 현재까지 해당 값이 몇 번이나 나왔는지를 넣었습니다. 또한, \(s_1, \cdots, s_j\) 가 하이퍼드롬인 경우도 있을 테니 m2에 \(0\)이 하나 존재한다고 미리 넣어두었습니다.

 

홀수 번째에 받는 값을 마지막 값으로 두었을 때, 몇개나 하이퍼드롬이 나올 수 있는지는 해당 값과 XOR를 했을 때에 비트 하나를 제외하고 나머지가 0인 값을 m2에서 찾아서 홀수 길이의 하이퍼드롬이 몇 개가 나왔는지를 알 수 있고, XOR를 했을 때에 0이 나오는 값을 m1에서 찾아서 짝수 길이의 하이퍼드롬이 몇 개가 나오는지도 알 수 있었습니다. 이후에 현재까지 prefix sum을 한 값을 m1이나 m2에 key로써 value 값을 \(1\)씩 올렸습니다. 

 

이렇게 구현했을 때 총 시간 복잡도는 \(O(53N)\)이 되었습니다. \(N\)개의 값별로 map 조회할 때 \(O(1)\), 그리고 하이퍼팰린드롬이 존재하는지 여부에서 모든 비트가 0인 경우 1개 + 비트가 딱 하나만 1인 경우 52개를 조회하다 보니 시간복잡도가 저렇게 됩니다.

 

제가 짠 코드는 아래와 같습니다.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll N;
    cin >> N;
    
    ll ans = 0;
    unordered_map<ll, int> m1;
    unordered_map<ll, int> m2;
    m2[0] = 1;
    
    ll bef_bitwise = 0;
    
    for(ll i =0; i<N; ++i){
        char s;
        cin >> s;
        ll val = 0;
        ll bitwise = 0;
        if(s >= 'a') val = s-'a'+26;
        else val = s - 'A';
        //cout << val <<"\n";
        bitwise = ((ll)1 << val);
        bitwise ^= bef_bitwise;
        bef_bitwise = bitwise;
        
        ll diff = bitwise;
        if(i%2 == 0){
            if(m1.find(diff) != m1.end())
            ans += m1[diff];
            for(ll j =0; j<52; ++j){
                ll offset = ((ll)1<<j);
                ll odd = diff ^ offset;
                if(m2.find(odd) != m2.end())
                ans += m2[odd];
            }
        }
        else {
            if(m2.find(diff) != m2.end())
            ans += m2[diff];
            for(ll j =0; j<52; ++j){
                ll offset = ((ll)1<<j);
                ll odd = diff ^ offset;
                if(m1.find(odd) != m1.end())
                ans += m1[odd];
            }
        }
        
        if(i%2 == 0){
            ++m1[diff];
        }
        else ++m2[diff];
    }
    
    cout << ans;
    return 0;
}
/*
만약에 홀수개 -> 홀수 하나, 나머지는 전부 짝수
만약에 짝수개 -> 전부 짝수

이를 bitwise로 푸는 방법도 있어는 보임.

tag : bitmasking, map

*/

이 문제를 푸는데는 대강 한 시간 정도 걸렸던 것 같습니다. 비트마스킹 문제를 오랜만에 풀어봐서 재밌었습니다.