BOJ 9935번: 문자열 폭발

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

문제 분류에는 스택이라고 표기되어 있지만, 꼭 쓰지 않아도 될 것 같아서 스택 없이 풀어보았습니다.

입력 받은 문자열을 우선 한 글자씩 결과를 저장할 문자열에 옮깁니다.

계속 옮겨주다가, 폭발 문자열의 마지막 글자와 같은 문자를 발견하면 비교를 시작합니다.

결과를 저장하는 문자열에 폭발 문자열이 있다면, idx를 줄여서 폭발 문자열 위에 입력 받은 문자열을 덮어씁니다.

원래 문자열이 끝나면, 결과 문자열의 끝에 NULL 캐릭터를 삽입합니다.

문제의 조건대로, 전부 폭발한 다음 남은 문자열이 없으면 (idx가 0이면) FRULA를 출력합니다.

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    char result[1000001]; // 결과를 저장할 char 배열 
    string input, tgt;
    int tgtLen, idx = 0;

    cin >> input >> tgt;
    tgtLen = tgt.length();

    for (int i = 0; i < input.length(); ++i) {
        result[idx++] = input[i]; // 입력된 문자열을 한 글자씩 옮김

        if (result[idx - 1] == tgt[tgtLen - 1]) { // 마지막으로 입력한 글자가 tgt의 끝 글자와 같으면 
            if (idx - tgtLen < 0) continue; // 예외 처리; result가 tgt보다 짧으면 검사할 필요 없음 
            bool hasTGT = true;

            for (int j = 0; j < tgtLen; ++j) {
                // idx 앞 쪽의 문자열이 tgt와 같은지 검사 
                if (result[idx - 1 - j] != tgt[tgtLen - 1 - j]) {
                    hasTGT = false;
                    break;
                }
            }
            if (hasTGT) idx -= tgtLen; // tgt가 존재하면 idx를 줄임 
        }
    }
    result[idx] = '\0'; // 결과의 끝에 NULL 문자 삽입. 
    idx == 0? printf("FRULA"): printf("%s", result);

    return 0;
}