백준 9935번 문자열 폭발

문제 링크입니다: https://www.acmicpc.net/problem/9935

문자열 처리가 메인이였던 스택 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 입력받은 문자열을 순회하면서 일단 결과 문자열에 추가합니다.

2. 폭탄 문자열의 마지막 문자를 발견하면 결과 문자열 끝에 폭탄이 있는지 확인하고 폭탄이 있다면 인덱스를 폭탄 문자열 길이만큼 빼서 폭탄을 제거합니다.

3. 2번을 마친 후 인덱스가 0이라면 폭탄문자열로만 구성된 문자열이였으므로 "FRULA"를 출력하고 인덱스가 1 이상이라면 해당 문자열을 출력합니다.

#include <iostream>

#include <string>

using namespace std;

 

const int MAX = 1000000 + 1;

 

string s, bomb;

char result[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> s >> bomb;

 

        int idx = 0;

        for (int i = 0; i < s.length(); i++)

        {

                 //일단 추가

                 result[idx++] = s[i];

                 //폭탄으로 추정되는 부분 문자열 발견

                 if (result[idx - 1] == bomb[bomb.length() - 1])

                 {

                         //기저 사례

                         if (idx - bomb.length() < 0)

                                 continue;

 

                         //폭탄 여부 파악

                         bool detected = true;

                         for(int j=0; j < bomb.length(); j++)

                                 if (result[idx - j - 1] != bomb[bomb.length() - j - 1])

                                 {

                                          detected = false;

                                          break;

                                 }

 

                         //폭탄 제거

                         if (detected)

                                 idx -= bomb.length();

                 }

        }

 

        if (!idx)

                 cout << "FRULA\n";

        else

        {

                 for (int i = 0; i < idx; i++)

                         cout << result[i];

                 cout << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~