[백준 17464] 알파벳 문자열

작성일 | In |

문제 링크

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

풀이

문자열에서의 순서가 중요하지 않기 때문에 비트로 관리할 수 있습니다. 비트로 관리한다면 or 연산으로 중복된 문자가 들어와도 처리가 가능하기 때문에 오른쪽 $r$을 고정하고 $l$을 $r$에서 시작해서 $1$까지 한칸씩 문자를 문자열에 추가해서 가짓수를 관리하면 $O(N^2)$으로 문제를 풀 수 있습니다.

$N≤10^5$이기 때문에 시간복잡도를 줄이기 위해 찾아야 하는 관찰이 있는데, 중복된 문자는 무시해도 된다는 것입니다. $CAAB$라는 문자열에서 $r$이 $4$일때를 관찰해보면

  1. $l=4$ : $B$
  2. $l=3$ : $AB$
  3. $l=2$ : $AB$
  4. $l=1$ : $ABC$

$A$가 중복해서 나타난 $l=2$는 무시하고 $l$을 $3$에서 $1$로 뛰어넘어도 정답을 찾는데에는 영향이 없습니다. 그러므로 중복된 문자는 넘어간다면 하나의 $r$에서 $l$은 최대 $26$번(알파벳의 개수)만 확인하면 됩니다. prefix max를 미리 구하고 각 $r$마다 정렬$O(Nw \log w)$로 문자열에 추가되는 문자의 순서를 구하면 $O(Nw)$만에 문제를 풀 수 있습니다.

$2^{26}$가지 문자열이 나올 수 있기 때문에 가짓수를 배열로 관리하지 못하지만 bitset을 이용하면 $2^{26}/64 = 1048576$정도로 충분히 관리할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int tc, n;
pair<int, int> mx[100100][26];
string s;
bitset<1<<26> b;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> tc;
    while(tc--){
        b.reset();

        cin >> s;
        n = s.size();
        for(int i=1;i<=n;i++){
            for(int j=0;j<26;j++){
                mx[i][j] = {s[i-1]-'A' == j ? i : mx[i-1][j].first, j};
            }
        }

        for(int i=1;i<=n;i++){
            int k = 0;
            sort(&mx[i][0], &mx[i][25]+1, greater<>());
            for(int j=0;j<26 && mx[i][j].first;j++){
                k |= 1 << mx[i][j].second;
                b.set(k, 1);
            }
        }

        cout << b.count() << "\n";
    }
}