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

📕문제

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

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

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

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

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

---

📕입력

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

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

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

---

📕출력

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

---

💡문제 해석

(이해하기 편하게 입력받은 문자열을 str, 폭발문자열을 bomb, 문자열 vector를 s라고 하겠다.)

• bomb를 포함해야 문자열을 폭발시킬수있다.
• str과 bomb의 길이 비교
  • bomb보다 s의 size가 작다면 폭발을 시킬 수없으므로 continue해줌.
  • bomb보다 s의 size가 크거나 같다면 폭발을 시킬 수 있음.
    • s의 끝열과 bomb의 끝열이 일치할 경우에 폭발가능
      • s에서 bomb의 size만큼 빼고 거기 index부터 bomb를 차례대로 비교
      • 만약 하나라도 bomb와 일치하지않다면 그때는 폭발시킬수 없음. (flag ==false)
      • 전부다 일치하다면 (flag==true)가 될것임.
  • 만약 flag가 true라면 폭발해야하므로 폭발문자열의 크기만큼 뒤에서 pop해줌.
• 이 과정을 모두 거치고 for문을 빠져 나왔을 때
  • s의 size가 0이라면 모든 문자열이 폭발한것이므로 "FRULA"를 출력함.
  • 0이 아니라면 s를 차례대로 출력함.

---

💡코드

/* 9935 골드4 문자열 폭발
내가 처음에 하는 방식은 문자열 처음 부터 차근차근 비교해서 하는것 --> 시간초과가 남.
왜 시간초과가 나지? O(n[문자열길이]) *O(폭탄길이) 라서?
어떻게 해야할까?
---내잘못 ..,
나는 그 폭발문자열에 포함되어있는 문자열만 만나면 지워줘야된다고 생각했지만 그 폭발문자열 전체를 지우는것이었다.
그래서 틀렸다.. 하나하나 비교해서 지웟으니까 틀리지,.,
예를 들어 c4가 있다면 ca4가 있으면 이건 못지우는 건데 내 코드로는 지운것이다. 그래서 틀린것이었고 내가 의도한 접근대로 하니 당연히 시간초과가 나는것이고,,
문제를 잘읽자.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
using namespace std;
string str, bomb;
vector<char> s;
string answer;
int idx = 0;
int main()
{
    cin >> str >> bomb;
    for (int i = 0; i < str.length(); i++)
    { //문자열을 더하다가 폭탄 만나면 터트려줌.
        s.push_back(str[i]);
        //꼭 입력받은 문자열의 크기가 폭탄의 길이보다 작다면? 폭발시킬 필요가 없다.
        if (s.size() >= bomb.size())
        {
            bool flag = true;
            if (s[s.size() - 1] == bomb[bomb.size() - 1])
            { //끝에 폭탄이 걸렷다면 그 이전 폭탄의 길이 까지 문자열을 검사해줌.
                for (int j = 0; j < bomb.size(); j++)
                {
                    if (s[s.size() - bomb.size() + j] != bomb[j])
                    {                 //문자열의 끝에서 폭탄의 길이만큼 뺴준뒤 차근차근 더해서 폭탄이 있는지 없는지 체크함.
                        flag = false; //폭발못할경우 false 폭발할경우 true
                        break;
                    }
                }
                if (flag == true)
                { //폭탄을 만났으면 해당하는 인덱스까지 빼준다.
                    for (int k = 0; k < bomb.size(); k++)
                    {
                        s.pop_back();
                    }
                }
            }
        }
    }
    if (s.size() == 0)
    { //만약 size가 0이라면 모든 문자열이 폭발된것.
        cout << "FRULA";
    }
    else
    {
        for (auto v : s)
        {
            cout << v;
        }
    }
}

---

 

👀느낀 점

• 처음에 하는 방식으로 풀었을 때는 시간 초과 or 틀렸다가 나왔다
  • 이유 : 문자열을 처음부터 하나하나 차근차근 비교해서 폭탄 문자열과 비교했다.
  • 틀림.
• 애초에 문제를 잘못 해석했었다.
  • 나는 만약 str이 abcde고, bomb가 ce라면 abd를 출력했었다.
  • 내가 이해한 것은 그냥 폭탄 문자열의 원소들을 하나하나 str과 비교해서 일치하면 지우는 것이지만 
  • 문제는 그 폭탄문자열 그대로를 포함하는 것을 지우고 싶어 했으므로 당연히 내가 하는 방식이 틀렸고, 시간 초과가 당연한 결과다.
• 시간초과를 위해서 다양한 접근을 해보자. 
• 그리고 문제를 잘읽자!