백준 9935번 문자열 폭발 (C++)

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

9935번: 문자열 폭발

문제 요약

 

1. 첫 번째 문자열(길이 1이상, 1,000,000이하)과 폭발 문자열(1이상 36이하)이 주어진다.

2. 문자열에 폭발 문자열이 포함되어있을 경우, 해당 폭발 문자열은 폭파되어 사라진다.

3. 폭파 된 뒤 새로 생긴 문자열에서도 폭발 문자열이 생길 수 있다.

4. 폭발 문자열이 문자열에 없을때까지 계속 폭파된다.

 

핵심 포인트

 

이 문제는 스택의 개념으로 접근하면 쉽게 풀릴 수 있습니다.

문제를 풀때 아래와 같은 실수들을 조심하면 됩니다.

 

1. find로 무작정 폭발 문자열을 제거하기

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string s,boom,temp="";
    cin >> s;
    cin >> boom;
    while(s.find(boom)!=s.npos){
        int pos = s.find(boom);
        s.erase(pos,boom.size());
    }
    if(s.size()==0) cout << "FRULA" << "\n";
    else cout << s << "\n";
    char c;

}

별 생각없이 단순하게 위와 같이 접근했지만 시간초과가 발생했습니다.

find함수로 문자열을 탐색하면 시간복잡도 O(n)이 소요되는데, 문자열의 최대길이가 1,000,000이기 때문입니다.

 

2. 스택의 개념을 미흡하게 활용

string s = "abcdedeff";
string boom = "def";

스택을 구현하여 s에 저장된 문자열을 하나씩 저장하고, boom에 저장되어있는 폭발문자열을 제거한다고 가정해봅시다.

중간에 def가 폭파되고 남은 문자열을 확인하면, 또 한번 def가 사라질 수있습니다.

이럴경우 stack의 top()에서 좀 더 앞의 요소까지 탐색해야하는 상황이 벌어지는데, 그 과정이 그리 쉽지 않습니다.

방법을 동원한다면 가능할 수 있겠지만 코드가 복잡해지는 상황이 발생할 수 있습니다.

 

 

문제 풀이

 

아래 전체 코드에서 부분적으로 설명을 진행하겠습니다.

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string s,boom,temp=""; // 1
    cin >> s;
    cin >> boom;
    for(int i=0; i<s.size(); i++){// 2
        temp+=s[i];
        if(temp.back()==boom.back()){ // 3
            bool ch = true;
            if(temp.size()<boom.size()) continue; // 4
            for(int j=0; j<boom.size(); j++){ // 5
                if(temp[temp.size()-boom.size()+j]!=boom[j]){
                    ch = false;
                    break;
                }
            }
            if(ch){ // 6
                for(int j=0; j<boom.size(); j++) temp.pop_back();
            }
        }
    }
    if(temp.empty()) cout << "FRULA" << "\n"; // 7
    else cout << temp << "\n";
    return 0;
}

(1) 문자열 s는 문자열 원문의 전문을 복사하고 boom에는 폭발 문자열을 저장합니다. temp는 stack처럼 활용하여 문자열을 저장할 변수입니다.

(2) 문자열 s의 사이즈만큼 for문을 돌립니다.

(3) 만약 temp에 저장된 문자열의 맨뒤(=stack의 top()에 해당됨)와 boom의 맨 뒤 값이 일치한다면...

-> (4) 만약 temp의 사이즈가 boom의 사이즈보다 작다면 폭발이 불가능하므로 continue를 진행합니다.

-> (5) 그렇지 않을 경우 boom의 사이즈만큼 for문을 돌립니다.

5번의 for문은 boom의 사이즈만큼 문자열 s에서 값을 확인하고 순차적으로 앞에서 뒤까지 boom의 문자열과 일치하는지를 확인하는 과정입니다. 포인트는 stack처럼 맨 뒤에서 하나씩 비교하는게 아니라, boom의 사이즈만큼 앞에서 뒤로 순차적으로 확인한다는 점입니다.

(6) 만약 ch가 true라면 폭발문자열이 존재한다는 뜻이므로, 폭발문자열의 사이즈만큼 temp의 맨 뒤에서부터 값을 삭제합니다.

(7) temp가 비어있을 경우 FRULA를 출력하고, 그렇지 않을 경우 temp자체를 출력합니다.