[C++]/백준 9935번 문자열 폭발

• 문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

• 입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

• 출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

• 예제 입력

mirkovC4nizCC44
C4

12ab112ab2ab
12ab

• 예제 출력

mirkovniz

FRULA

• 접근방식

폭발, 짝짓기 라는 단어가 나오면 stack을 이용해서 풀 수 있다.

입력 받은 문자열 하나씩 스택에 넣고 스택의 크기가 폭발 문자열의 크기보다 크거나 같다면 스택의 상단 부분과 폭발 문자열 끝 부분을 비교해서 그것도 같다면 빈 문자열에 폭발 문자열의 크기만큼 스택을 빼서 넣고 비교한다. 즉, 다시 말하자면

1. 입력 받은 문자열을 전부 순회하면서 하나씩 스택에 넣기
2. 순회하면서 스택의 크기가 폭발 문자열의 크기보다 크거나 같다면
3. 스택 상단 부분과 폭발 문자열 끝 부분을 비교해서 같다면
4. 빈 문자열에 폭발 문자열의 크기만큼 스택을 빼서 넣고 비교(스택에서 빼온 부분은 반대로 되어 있어서 뒤집어 줘야함)
5. 만약 폭발 문자열이 아니면 다시 스택에 넣어주기
6. 만약 폭발 문자열이라면 스택에 다시 넣지 않고 다시 순회하기
7. 순회가 끝나고 스택이 비어있으면 FRULA 출력, 아니라면 결과 문자열에 스택의 윗부분 하나씩 빼고 뒤집기

 

stack 말고도 erase를 사용해서 풀 수 있다.

1. 입력 받은 문자열을 전부 순회하면서 결과 문자열에 붙힘
2.순회하면서 결과 문자열의 크기가 폭발 문자열의 크기보다 크거나 같으면
3. 결과 문자열의 크기 - 폭발 문자열의 크기 ~ 폭발 문자열의 크기까지가 폭발 문자열과 같다면 (즉, 끝에 폭발 문자열의 크기만큼의 자리)
4. 해당 부분을 제거하면서 순회
5. 순회가 끝나고 결과 문자열이 비어있으면 FRULA출력, 아니라면 결과 문자열 출력

• 코드

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

using namespace std;

string s, bomb, result;
stack<char> stk;

int main()
{
    cin >> s >> bomb;

    for (char a : s)
    {
        stk.push(a);
        if (stk.size() >= bomb.size() && stk.top() == bomb[bomb.size() - 1]) // 스택의 크기와 폭발 문자열 크기를 비교후 스택의 상단 부분과 폭발 문자열 끝 부분 비교
        {
            string temp = "";
            for (char i : bomb)
            {
                temp += stk.top();
                stk.pop();
            }
            reverse(temp.begin(), temp.end()); // 스택에서 빼온 부분은 반대로 되어 있기 때문에 다시 뒤집기
            if (bomb != temp) // 폭발 문자열이 아니면 다시 집어넣기
            {
                for (char i : temp)
                {
                    stk.push(i);
                }
            }
        }
    }

    if (!stk.size())
    {
        cout << "FRULA";
    }
    else
    {
        while (stk.size())
        {
            result += stk.top();
            stk.pop();
        }
        reverse(result.begin(), result.end());
        cout << result;
    }

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

string s, bomb, result;

int main()
{
    cin >> s >> bomb;

    for (char a : s)
    {
        result += a;
        if (result.size() >= bomb.size() && result.substr(result.size() - bomb.size(), bomb.size()) == bomb)
        {
            result.erase(result.end() - bomb.size(), result.end());
        }
    }

    if (!result.size())
    {
        cout << "FRULA";
    }
    else
    {
        cout << result;
    }
    return 0;
}

 

• 문제링크 : https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발