백준 27397 - 문자열 변환과 쿼리 2 (C++)

문제

• 문제 링크

  
   BOJ 27397 - 문자열 변환과 쿼리 2 
  

• 문제 요약

문자열 $S$가 주어진다.
$N$개의 쿼리에 대해 그에 맞는 처리를 해보자.

• 제한

TL : $3$ sec, ML : $512$ MB




$1 ≤ len(S) ≤ 300,000$

$1 ≤ N ≤ 300,000$

$1 ≤$ $len(S)$ $*$ $count(n_2)$ $≤ 10^7$

알고리즘 분류

• 자료 구조(data structures)
• 문자열(string)
• 해시를 사용한 집합과 맵(hash _ set / map)

풀이

문자열 변환과 쿼리 $1$ 과 별반 다를 게 없다.

쿼리 내용 그대로 이번엔 최대 연속 구간을 세주면 되겠다.
이 역시 세번째 제한으로 인해 복잡도가 보장된다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
string s;
char M[130];
int n;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (n = 65; n < 123; n++) M[n] = n;
    cin >> s >> n;
    for (char p, q, i; n--;)
        if (cin >> i; i & 1)
        {
            cin >> p >> q;
            for (i = 65; i < 123; i++)
                if (M[i] == p)
                    M[i] = q;
        }
        else
        {
            int i(1), c(1), r(1);
            for (; i < (int)s.size(); i++)
                M[s[i]] == M[s[i - 1]] ? c++, r = max(r, c) : c = 1;
            cout << r << '\n';
        }
}

comment

끝