[ 백준 ] 9935 / 문자열 폭발

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
75/228
post-thumbnail

# Appreciation

/*
 * Problem :: 9935 / 문자열 폭발
 *
 * Kind :: Simulation + Data Structure
 *
 * Insight
 * - 문자열을 읽다가 폭발 문자열을 만나면 그 문자열을 지워준다
 *   + 문자열 = mirkovC4nizCC44
 *     폭발 문자열 = C4
 *     # m
 *       mi
 *       mir
 *       mirk
 *       mirko
 *       mirkov
 *       mirkovC
 *       mirkov(C4) => Bomb!
 *       mirkovn
 *       mirkovni
 *       mirkovniz
 *       mirkovnizC
 *       mirkovnizCC
 *       mirkovnizC(C4) => Bomb!
 *       mirkovniz(C4) => Bomb!
 *
 * Point
 * - 주어진 문자열만을 이용해 폭발 문자열을 지워주면 시간초과가 난다
 *   + 문자열 = CCC...CCC (len=10^6)
 *     폭발 문자열 = C
 *     # http://www.cplusplus.com/reference/string/string/erase/
 *       -> 'erase'
 *          Complexity
 *          Unspecified, but generally up to linear in the new string length
 *          => 그러니 폭발이 끝난 후 남은 문자열을 따로 선언해주어 이를 이용하자
 *
 * - 폭발이 끝난 후 남은 문자열을 스택으로 생각하면 편하다
 *   + top 에 있는 문자가 폭발 문자열의 맨 뒤 문자와 같은지 확인한 후,
 *     스택에 쌓인 문자들이 폭발 문자열들의 문자들과 같다면 삭제시켜준다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    string S; cin >> S;
    string W; cin >> W;

    // Process
    int SL = S.length();
    int WL = W.length();

    string A; /* 폭발이 끝난 후 남은 문자열 */
    for (int i=0; i<SL; i++) {
        A.push_back(S[i]);
        if (A.back() == W.back() && A.length() >= WL) {
            int AL = A.length();
            if (A.substr(AL-WL, WL) == W) {
                A.erase(AL-WL);
            }
        }
    }

    // Control : Output
    cout << ((A.empty()) ? "FRULA" : A) << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글