BOJ 9935: 문자열 폭발 [C++]

9935번: 문자열 폭발

 

 

12트 만에 풀었다...

처음엔 string의 find, replace를 써서 풀어보려 했으나 시간초과.

두 번째는 정규식 써서 풀어보려 했으나 역시 시간초과.

질문 게시판을 보니 스택 문제라고 하여 '이게 스택 문제라고?' 생각하다

'큐 두 개를 써서 요리조리 옮기면 어떨까' 하여 해 봤지만 역시 시간초과.

char 배열과 큐 하나만 써서 해봤지만 이것도 시간초과.

 

그러다 스택에 문자를 담지 말고, 폭발 문자열인지 검사하는 인덱스를 넣기로 하고 코드를 작성했다.

예제는 맞았으나 2%에서 틀려 뭐가 문젠지 고민하다 다시 질문 게시판의 반례들을 뒤져봤다.

 

글 읽기 - 문자열 폭발 어렵네요... 반례찾기 부탁드립니다 (설명있음)

이 글의 예제를 통해 해결할 수 있었다.

틀린 원인은 검사하던 인덱스를 스택에 저장했을 때

1. 그 뒤로 폭발 문자열이 될 수 없는 문자가 오거나
2. 다른 폭발 문자열 검사 시퀀스가 시작되거나

하면 이전에 검사하던 것들은 어떻게 해도 폭발 문자열이 될 수 없기 때문에,

아예 스택을 비워줘야 하는 것이었다.

 

#include <iostream>
#include <stack>

int main() {
    std::string answer;         // 정답을 담을 string
    std::stack<int> indexTrace; // 폭발 문자열 검사 인덱스를 담는 stack

    std::string input;          // 입력 문자열
    std::cin >> input;

    std::string explode;        // 폭발 문자열
    std::cin >> explode;

    int explodeIndex = 0;
    for (int i = 0; i < input.size(); i++) {
        // 정답에 추가
        answer.push_back(input[i]);

        if (input[i] == explode[explodeIndex]) {
            // 폭발 문자열에 해당한다면 인덱스 증가
            explodeIndex++;
        } else {
            // 검사하던 인덱스 스택에 저장
            indexTrace.push(explodeIndex);
            
            // 처음부터 검사
            explodeIndex = 0;                   
            if (input[i] == explode[explodeIndex]) {
                explodeIndex++;
            } else {
                // 폭발 문자열이 완성될 수 없도록 끊어졌기 때문에
                // 이전에 검사하던 인덱스들을 모두 버려야 함
                while (!indexTrace.empty()) {
                    indexTrace.pop();
                }
            }
        }

        // 폭발 문자열 완성되면 그 크기만큼 정답에서 삭제
        if (explodeIndex == explode.size()) {
            for (int j = 0; j < explodeIndex; j++) {
                answer.pop_back();
            }
            
            // 이전에 검사하던 인덱스가 있다면 복구, 그렇지 않다면 0부터 검사
            if (!indexTrace.empty()) {
                explodeIndex = indexTrace.top();
                indexTrace.pop();
            } else {
                explodeIndex = 0;
            }
        }
    }

    if (answer.empty()) {
        std::cout << "FRULA\n";
    } else {
        std::cout << answer << "\n";
    }

    return 0;
}