[BOJ] 문자열 폭발_9935 C++ 풀이

문제

입력된 문자열이 폭발 문자열을 포함하고 있으면 모든 폭발 문자열을 폭발 시키고 폭발 문자열이 폭발되어 이어져서 새로 만들어진 문자열에도 폭발 문자열이 생성되었을 시, 생성된 폭발 문자열 또한 폭발 시켜준다. 폭발 문자열이 문자열에 없을 때 까지 반복한다. 폭발을 시키다가 남아 있는 문자가 더이상 없을 경우에는 “FRULA”를 출력한다.

접근 방법

입력 받은 문자열 str을 순회하면서 result 배열에 문자를 삽입해 주었다.

순회 과정에서 result 배열의 마지막 인덱스와 폭발 문자열의 마지막 인덱스가 같다면

result 배열과 폭탄 배열의 인덱스를 서로 비교해 가며 폭탄 여부를 판단하였다.

폭탄 문자열을 발견하였다면 result 배열의 인덱스를 폭탄 문자열 길이 만큼 빼주고 만약 위 과정을 수행한 후 인덱스가 0이라면 폭탄 문자열로만 구성된 문자열을 뜻하므로 “FRULA”을, 인덱스가 1 이상 이라면 result 배열에 저장된 결과 값을 출력하였다.

구현

#include<iostream>
#include<string>
using namespace std;
#define MAX 1000001

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string str, bomb;
    char result[MAX];
    bool check=true; //폭탄이면 true
    int idx=0;
    int len_str, len_bomb;

    cin>>str;
    cin>>bomb;
    len_str=str.length();
    len_bomb=bomb.length();

    for(int i=0; i<len_str; i++)
    {
        result[idx++]=str[i];

        if(idx<len_bomb) continue; 

        if(result[idx-1]==bomb[len_bomb-1]) //문자열의 끝문자가 폭탄문자열의 끝 문자와 같은경우 폭탄으로 의심하고 확인 처리
        {
            for(int j=0; j<len_bomb; j++)
            { // result문자열의 뒤와 폭탄 문자열의 뒤에서 부터 비교해 가며 폭탄 인지 확인
                if(result[idx-j-1]!=bomb[len_bomb-j-1])
                {
                    check=false; //문자가 같지 않으므로 폭탄 아님
                    break;
                }
            }
            if(check) idx-=len_bomb; //폭탄인 경우
        }
        check=true;
    }

    if(!idx) cout<<"FRULA";
    else
    {
        for(int i=0; i<idx; i++)
        {
            cout<<result[i];
        }
    }
    return 0;
}

BOJ_문자열 폭발