[C++] 백준/BOJ - 9935 : 문자열 폭발

---

문제 이해 단계

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

첫 번째 줄에 문장이 주어지고, 두 번째 줄에 폭발 문자열이라는 특정 키워드가 주어진다.

문장에서 폭발 키워드가 있으면 그 부분을 지운다.
그리고 문장을 이어 붙인다.

문장을 이어 붙였을 때, 또 키워드가 완성된다면 그 부분을 지운다.

이런 식으로 모든 폭발키워드를 지운 후, 남은 문장을 출력한다.

 

 

---

문제 접근 단계

제한사항부터 보자. 문장의 길이는 최대 1,000,000이다.
그리고 폭발 문자열은 36개까지이다.

처음에는 문자열 탐색으로 키워드를 찾고,
이어 붙이고 하는 과정을 반복하려고 했는데

문장의 길이가 10^6이기 때문에 10^6*10^6 = 10^12로 시간초과가 뜬다.
그래서 다른 방법을 찾아봐야 한다.

 

---

풀이 로직

여기서 중요한 것은 키워드를 찾는 것과
키워드를 삭제한 후 이어 붙이는 것이다.

문자열을 직접 이어 붙이는 것은 상당히 힘들기 때문에
문자열 하나하나를 다 분리해서 보는 것이 더 나을 것 같다.

결국 문장과 키워드라는 것도 순서가 중요한 것이기 때문에,
큐나 스택에 넣어줌으로써 순서를 유지해 준다.

나는 스택을 사용해서 순서를 유지해 주고,
현재까지 스택에 넣은 값들 중 키워드에 속하는 것이 있는지를 확인하는 작업을 진행했다.

스택을 사용해 준 이유는,
스택을 이용하면 pop을 할 때 넣었던 값 중 가장 최신 값을 얻을 수 있기 때문이다.

로직을 그림으로 나타내보면 이런 식으로 된다.

예제 케이스 1

문장을 앞에서부터 탐색하는데, 폭발 문자열과 상관이 없는 문자가 들어오거나,
폭발 문자열의 마지막 글자(여기서는 '4')가 아니라면 무조건 큐에 넣는다.

C까지 스택에 넣었을 때

그래서 C까지는 그냥 스택에 들어간다.
전환점은 폭발 문자열의 마지막인 '4'에 도달했을 때 발생한다.

'4'에 도달했다면 '4'를 스택에 넣고
폭발 문자열의 길이만큼 스택에서 요소를 뺀다.

그리고 그 순서를 역으로 배열하여
폭발 문자열과 키워드가 일치하는지를 확인한다.

위 그림에서는 꺼내서 뒤집은 문자열과 폭발 문자열이 전부 "C4"로 일치한다.

이런 경우에는 스택에서 뽑아준 그 상태로 바로 다음 탐색으로 넘어간다.

만약 일치하는 않는 경우,
스택에서 뽑아준 원소들을 다시 원래 순서대로 스택에 넣어준다.

이러한 과정을 끝까지 반복한 후,
스택에 남아있는 모든 요소를 뽑아준 뒤 반대로 뒤집어 출력한다.

로직을 생각해 내기가 어렵지, 풀이는 사실 간단하다.
바로 문제 구현 단계로 가보자.

 

 

---

문제 구현 단계

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    string word,boom;
    cin >> word >> boom;

    stack<char> s;

    string ans;
    ans.reserve(1000000); // 미리 할당해둠으로서 시간복잡도를 줄임
    for(int i = 0; i < word.length(); i++){

        s.push(word[i]); // 스택에 넣음

        // 현재 탐색하는 문장의 단어가 폭발 문자열의 마지막 단어 && 스택에 있는 원소가 폭발 문자열 갯수 이상일때
        if(word[i] == boom[boom.length()-1] && s.size() >= boom.length()){
            string tmp;
            // 폭발 문자열의 길이만큼 스택에서 뺌
            for(int j = 0; j < boom.length(); j++){
                tmp.push_back(s.top());
                s.pop();
            }
            reverse(tmp.begin(),tmp.end()); // 뺀 문자열 뒤집기

            // 뒤집은 문자열과 폭발문 문자열 같은지 판단
            if(tmp.compare(boom) != 0){
                // 다르다면 다시 스택에 넣음
                for(int i = 0; i < tmp.length(); i++) s.push(tmp[i]);
            }
        }
    }

    // 스택에 남은 원소들을 ans에 넣음
    while(!s.empty()){
        ans.push_back(s.top());
        s.pop();
    }
    reverse(ans.begin(),ans.end()); // 뒤집어서 순서대로 나오게함
    if(ans.empty()) cout << "FRULA"; // 스택이 비어있다면 모두 폭발한 것
    else cout << ans;
}

코드는 간단하다.
위에서 말한 것처럼 문장을 첫 인덱스부터 탐색해 준다.

중간에 마지막단어를 판단해 주는 조건을 제외하고
스택에 사이즈를 판단해 주는 조건을 추가해 준 이유는,

어차피 폭발문자열의 길이만큼 존재하지 않는다면 일치하지 않기 때문이다.

이 과정을 바디 반복하고 ans에 남은 원소들을 모두 넣고 이를 뒤집어 출력한다.

그럼에도 ans가 비어있다는 것은 모두 폭발했다는 것이기 때문에
비어있음을 뜻하는 FRULA를 호출한다.

 

 

---

시행착오

푸는데 정말 오래 걸렸다. 한 4시간 정도 걸린 것 같다.

처음에는 문자열로 풀면 될 줄 알고 쉬운 문제인 줄 알았는데 시간 초과와 싸우는 문제였다.

진짜 하루종일 싸운 듯하다.
별의별 방법을 다 써본 것 같다.

근데 정작 푼 방법은 간단하니까 좀 허무하긴 하다.

 

생활비..

https://toss.me/howudong

howudong님에게 보내주세요