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

문제

• 문제 링크

  
   BOJ 27396 - 문자열 변환과 쿼리 
  

• 문제 요약

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

• 제한

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




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

$1 ≤ N ≤ 300,000$

$1 ≤$ 유형 $2$로 출력되는 문자의 총 수 $≤ 10^7$

알고리즘 분류

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

풀이

쿼리 1에서 $S$를 돌아보며 일일히 바꿔주고 있으면 당연히 $TLE$ 다.
등장하는 문자가 알파벳으로 한정됨에 따라 이에 맞는 카운트 배열을 만들어 주자.

$M[x] = y$ : 문자 $x$가, 현재 문자 $y$로 바뀐 상태.

쿼리 2는 $S$를 순회하며 $0, 1, ... n - 1$번 인덱스에 대해 $M[i]$를 출력해주면 된다.
이는 세번째 제한으로 인해 복잡도가 보장된다.

전체 코드

#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
        {
            for (char i : s) cout << M[i];
            cout << '\n';
        }
}

comment

끝