[백준, C++] 9935 - 문자열 폭발

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

9935번: 문자열 폭발

 

문제 분석

입력으로 2개의 문자열이 주어진다. 먼저 입력된 문자열은 어떻게 보면 폭발의 피해자 (?) 이다. 두 번째로 주어지는 문자열이 폭발 문자열인데, 먼저 입력된 문자열에서 폭발 문자열이 있다면 해당 부분을 폭발시킨(도려낸)다. 만일 폭발 문자열에 의해 폭발되고 나서, 문자열 내에 또 폭발 문자열이 포함되어 있으면 여전히 터진다. 그래서 더 이상 폭발하지 않을 때까지 계속 이 과정을 반복한 후, 그 결과를 출력하는 문제이다.

 

처음에는 되게 쉽다고 생각했는데, 풀면서 시간 초과의 벽에 막혔었다. 일단은 시간 초과된 풀이 말고, 결국 맞춰낸 정답 풀이를 먼저 설명한 후 시간 초과된 풀이와 시간 초과된 이유에 대해 알아보는 순서로 진행해보겠다.

 

아마 나 뿐만 아니라 이 글을 검색해서 보게 되는 여러분들도 이 문제를 보자마자 아래 두 가지 중 하나의 방법을 생각하셨을 것 같다.

 

1. 더이상 폭발 문자열을 포함하지 않을 때까지, 문자열을 처음부터 순회하며 폭발 문자열이 있는지 체크하고 있다면 폭발 문자열을 날려버린다.

 

2. 1번 방법을 사용하면 너무나도 원시적이기 때문에 (문자열의 길이가 최대 100만), 문자열을 매번 처음부터 순회하는 것이 아니라 폭발 문자열의 맨 앞 글자의 위치(인덱스)를 stack 같은 자료구조에 담아두고, stack에서 폭발 문자열의 맨 앞 글자 위치를 pop()하면서 폭발 문자열을 도려낸다.

 

나는 1번의 방법이 너무나도 오랜 시간이 걸릴 것이라 머리로 대충 생각했기 때문에(시간 제한이 2초니까 ... 약 2억 번 연산 내로 끝내야 하는데 1번 방식으로 하면 100만의 제곱만큼이나 시간이 걸릴 것 같아서) 2번의 방법을 생각해 시도했다. 문자열을 도려내는 방법으로는 substr()을 통해 폭발 문자열이 등장하기 전까지의 문자열 + 폭발 문자열을 지나치고 나서의 문자열 형식으로 추출해내거나, erase()를 통해 폭발 문자열만 지우는 방법을 생각했고 구현했다. 하지만 이 방법은 시간 초과가 난다. 그 이유는 뒤에서 설명하기로 했고, 내 풀이는 이렇다.

 

3. stack에 문자열을 처음부터 한 글자씩 push()한다. 방금 push()한 그 글자가 폭발 문자열의 맨 마지막 글자와 같다면, stack에서 폭발 문자열의 길이만큼 문자를 빼내고 그걸 뒤집는다(stack은 LIFO니까). 그리고 스택에서 꺼내서 뒤집은 그 문자열이 폭발 문자열과 같다면, 그 문자열을 다시 stack에 넣을 이유가 없다. 하지만 그 문자열이 폭발 문자열과 다르다면, 그 문자열은 다시 고이 stack에 push()한다. 즉, 한 글자씩 확인하면서 폭발 문자열의 마지막 글자가 push()될 때마다 폭발 문자열의 길이만큼 꺼내서 폭발 문자열인지를 확인하는 방법이다. 이를 통해 제한 시간 안에 문제를 해결할 수 있다.

 

코드

#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>

using namespace std;

string input;
string target;
string result;

stack<char> st;

void getInput();
void solve();
void printResult();

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> input;
    cin >> target;
}

void solve() {
    for (int i = 0; i < input.length(); i++) {
        st.push(input[i]);

        if (input[i] == target[target.length() - 1] && st.size() >= target.length()) {
            string str = "";
            for (int j = 0; j < target.length(); j++) {
                str += st.top();
                st.pop();
            }
            reverse(str.begin(), str.end());

            if (str != target) {
                for (int k = 0; k < str.length(); k++) {
                    st.push(str[k]);
                }
            }
        }
    }

    while (!st.empty()) {
        result += st.top();
        st.pop();
    }

    reverse(result.begin(), result.end());
}

void printResult() {
    cout << (result.length() == 0 ? "FRULA" : result) << "\n";
}

 

코드 설명

처음 입력으로 받은 문자열을 input, 폭발 문자열을 target이라고 이름지었다. 그리고 폭발 문자열을 모두 폭발시킨 후 남은 문자열을 result라고 이름지었다. 문제를 풀어나가는 과정은 input 문자열을 순회하면서 시작한다. input[i]를 stack에 차례로 push()하는데, 이 때 input[i]가 target[last]와 같다면 방금 집어넣은 그 문자가 폭발 문자열일 수 있다는 의심을 하면서 시작한다. 그래서 stack에서 target.length()만큼 문자를 pop()하면서 그 문자들을 문자열(str라 이름지었다)로 만드는데, stack은 LIFO기 때문에 만들어진 문자열은 역순이 된다. 그래서 <algorithm> 헤더의 reverse() 메서드를 사용했다(직접 뒤집어도 된다).

 

이렇게 pop()한 문자들의 문자열(str)과 폭발 문자열(target)을 비교한다. 만일 str이 폭발 문자열과 같다면, str은 어차피 터질 놈들이니까 stack에 다시 넣어주지 않는다. 하지만 str이 폭발 문자열과 다르다면, 이 문자열 녀석들은 터질 놈들이 아니니까 다시 stack에 고이 넣어둬야 한다. 이렇게 하면 input을 1번만 순회하면서 문제를 풀 수 있다.

 

input을 한 바퀴 다 순회하고 나서는, stack에서 모든 문자들을 꺼내 문자열(result)로 만든다. 역시, 한 번 더 stack은 LIFO기 때문에 reverse()를 통해 뒤집어준다. 그리고 만일 result가 빈 문자열이라면 문제에서 시킨대로 "FRULA"를 출력하고, 빈 문자열이 아니면 result 그 자체를 출력해준다.

 

시간 초과 코드

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

string input;
string target;

void getInput();
void solve();
void printResult();

void sliceIfMatch(int);

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> input;
    cin >> target;
}

void sliceIfMatch(int index) {
    if (index + target.length() > input.length()) {
        return;
    }
    
    if (input.substr(index, target.length()) == target) {
        input.erase(index, target.length());
    }
}

void solve() {
    stack<int> target0Index;

    for (int i = 0; i < input.length(); i++) {
        if (input[i] == target[0]) {
            target0Index.push(i);
        }
    }

    while (!target0Index.empty()) {
        int index = target0Index.top();
        target0Index.pop();

        sliceIfMatch(index);
    }
}

void printResult() {
    cout << (input.length() == 0 ? "FRULA" : input) << "\n";
}

초반에 구상하고 구현했던 코드 중 하나를 가져왔다. target0Index라는 stack은 target(폭발 문자열)의 첫 번째 문자와 일치하는 문자가 input에서 나타나는 인덱스를 담는 stack이다. 그래서 먼저 input을 한 바퀴 순회하면서 target0Index에 target[0]이 등장하는 인덱스를 push()했다. 그 후, target0Index가 empty()일 때까지 반복문을 통해 sliceIfMatch()라는 메서드를 호출하며 폭발 문자열이 input 안에 존재한다면 slice하도록, 즉 도려내도록 했다.

 

큰 관점에서 봤을 때, 정답 코드와 크게 시간 복잡도에서의 차이가 있을 것 같지는 않다. 그래서 굉장히 끙끙댔고, 풀다가 백준 질문 게시판을 뒤지기도 했다. 놀랍게도 이 문제는 약 7년 전부터 질문이 쌓이고 쌓여서 한 8~9페이지 정도의 질문이 있었다. 그 중 나는 이 질문을 보고 erase를 사용해 구현하는 방향은 시간 초과를 받을 게 뻔하구나 를 느꼈다.

 

https://www.acmicpc.net/board/view/34565

글 읽기 - ★★★★★★ 문자열 폭발 FAQ ★★★★★★

 

C++에서는 STL(Standard Template Library)의 시간 복잡도를 명확하게 제시하지 않는다고 한다. 하지만 몇몇 영문 사이트들을 참고한 결과 string의 erase는 O(N)이 소요된다고 한다. 개인적인 추측으로는 erase를 하고 나서 뒤의 원소들을 앞으로 땡겨와야 하기 때문인 것 같다. 또한 위에서 첨부했던 백준 질문 게시판의 글에서는 문자열의 중간을 한 번 지울 때마다 O(N)씩 걸린다고 하니, erase()의 다른 오버로딩 형태들(내가 사용한 startIndex, eraseSize를 전달하는 erase())이 기본적으로 문자 하나를 지우는 erase()를 반복적으로 호출한다고도 추측할 수 있을 것 같다. (여담으로 내부 구조를 훤히 보여주지 않는 건 정말 아쉬운 점인 것 같다)

 

정리하자면, string의 erase 메서드를 사용하면 O(N)이 소요되기 때문에 내 정답 코드처럼 stack만을 활용하는 것보다 훨씬 시간이 걸리게 된다. substr()을 통해 폭발 문자열의 앞 뒤만 잘라내고 합쳐서 취하는 방법도 생각해봤는데, 문자열과 문자열을 더하는 것은 O(N+M)이 걸린다고 하니 erase()와 큰 차이가 없을 것 같다(고 추측만 해서 짜증난다 ... 속 시원하게 알고싶다).

 

은근히 C++은 폐쇄적인 언어같다는 생각을 잠깐 해보며 ... 하지만 Java로 코딩테스트를 준비하기에는 입출력이 너무 귀찮은 문제 ... 가 있고 그냥 Kotlin을 코딩테스트 주언어로 준비를 미리 해볼 걸 하는 생각도 든다만 C++의 잡기술에 익숙해져버렸다.