백준 9548 - 무제 (C++)

문제

• 문제 링크

  
   BOJ 9548 - 무제 
  

• 문제 요약

본문에 써있는 내용을 그대로 가져와 보겠다.

"그냥 단순히 문자열 조작 연산을 구현하는 문제이다. 문제 이름은 딱히 필요가 없어서 짓지 않았다."


• 제한

TL : $10$ sec, ML : $256$ MB




$1 ≤$ 테스트 케이스의 수 $≤ 100$

$1 ≤ |S| ≤ 10^6$

$S$와 $R$은 항상 알파벳 소문자로만 구성되어 있으며, 연산의 결과로 $S$의 길이가 $10^6$을 넘어가는 경우는 없다.

출력되는 문자의 개수의 합은 모든 테스트 케이스에서 $10^6$을 초과하지 않는다.

알고리즘 분류

• 자료 구조 (data_structures)
• 문자열 (string)
• 로프 (rope)

풀이

문자열 조작을 효율적으로 수행할 수 있게 해주는, $rope$라는 자료구조가 있다. 내부는 $B$+ $Tree$와 비슷하게 구현되어 있다고 한다.

상당히 그뭔씹스러운 자료구조이고, 문자열 알레르기가 있는 나로선 $gcc$가 없었다면 아예 몰랐을 자료구조이다.

약 두 달 전 이 문제 에서 $gcc$ 확장 라이브러리인 $PBDS$ 자료구조를 이용했었다.
이번에도 $gcc$의 힘을 빌려, $rope$ 자료구조를 이용해보았다.

사용법은 일반 $string$ 객체에서 지원하는 인스턴스 함수를 쓰는 것처럼 친숙하다.

경험 삼아 써먹어 봤는데, 또 쓸 일이 있을지는 잘 모르겠다.
$PBDS$는 그래도 종종 써먹을 일이 있을 것 같았는데..

전체 코드

#include<bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--)
    {
        string s; cin >> s;
 
        rope <char> rp(s.c_str());
        for (string op, r; cin >> op, op != "END";)
        {
            if (op == "I")
            {
                int x; cin >> r >> x;
                rp.insert(x, r.c_str());
            }
            else
            {
                int x, y; cin >> x >> y;
                cout << rp.substr(x, y - x + 1) << '\n';
            }
        }
    }
}

comment

끝