문제 링크

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.


문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.



접근 과정

  1. 첫 풀이는 단순하게 하나씩 폭발 문자열을 지워가며 구현. 너무 당연하게도 시간초과를 마주할 수 있었다.
  2. 문제 분류에 스택이 있던 것에서 힌트를 얻어 문자열을 하나씩 비교하며 스택에 push하고 연속적으로 일치한 경우 폭발 문자열의 길이만큼 스택에서 pop하는 식으로 구현하였다. 이렇게 구현하면 O(N)의 시간으로 전체 문자열을 탐색 할 수 있다.
  3. 라고 생각은 잘 했지만 구현에서 실수가 있어 몇 번 틀리고 말았다. 스택에서 폭발 문자열을 제거한 후 다시 일치하던 위치 부터 비교해야 하는데 다시 처음 부터 비교해서 생긴 문제였다. 이를 해결하기 위해서 반복문 내에서 조건에 따라 커서 인덱스의 위치를 잘 조절해야 했는데 이 부분이 조금 어려웠던 것 같다. 정답 비율이 낮은 이유가 있는듯.

스택 상태의 변화

스택 상태의 변화

무슨 생각인지 문자열의 끝에서 부터 탐색하도록 구현했는데 하고보니 앞부분에서 탐색을 시작해도 구현하는데 문제는 없을 것 같다.


소스 코드

#include <iostream>
#include <string>
#include <vector>

void printStack(std::vector<std::pair<char, int> >& s) {
    for (unsigned int i = 0; i < s.size(); ++i) {
        std::cout << s[i].first << " | ";
    }
    std::cout << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

    std::string originStr;
    std::string boomWord;
    std::vector<std::pair<char, int> > record;

    std::cin >> originStr;
    std::cin >> boomWord;

    int i = originStr.size() - 1;
    int bwLen = boomWord.size();
    int bwCur = bwLen;
    while (i >= 0) {
        --bwCur;
        if (bwCur != bwLen - 1 && originStr[i] != boomWord[bwCur]) {
            bwCur = bwLen;
            continue;
        }

        if (originStr[i] != boomWord[bwCur]) {
            if (bwCur != bwLen - 1) {
                bwCur = bwLen;
                continue;
            }
            bwCur = bwLen;
        }

        record.push_back(std::pair<char, int>(originStr[i], bwCur));

        if (bwCur == 0) {
            for (int k = 0; k < bwLen; ++k) {
                record.pop_back();
            }
            bwCur = record.empty() ? bwLen : record.back().second;
        }

        --i;
    }

    if (record.empty()) {
        std::cout << "FRULA";
    } else {
        for (int k = record.size() - 1; k >= 0; --k) {
            std::cout << record[k].first;
        }
    }
    
    return 0;
}