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

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

 

평범한 문자열1개와 폭발 문자열1개를 입력받고, 평범한 문자열에서 폭발 문자열은 모두 사라지게 한 결과를 출력하는 문제

폭발문자열이 사라짐으로 인해 합쳐진 문자열이 또다시 폭발 문자열을 포함한다면 그것도 폭발시켜야함!

 

접근방법

Swift String의 range와 replacesubrange를 사용해보았는데 대차게 시간초과 떠서,,얌전히 C++로 풀었다네요ㅋㅋ,,

Stack문제는 Stack으로..

접근방법을 한마디로 요약하면 "Stack에 문자를 하나 넣을 때 마다 폭발물을 검사하자"입니다.

평범한 문자열을 모두 순회하면서 한글자씩 Stack에 넣을 건데요, 이때 한글자가 들어갈 때마다

폭발물 문자열 길이 만큼 스택 상단의 문자열을 뽑아서 폭발물인지 확인하고, 맞으면 다 빼버리고, 다르면 그대로 둡니다.

 

이때 vector to string 방식으로는 string 생성자를 썼습니다. 아주 요긴했습니다.

string 변수명(vector시작인덱스, vector끝인덱스); 이러면 vector에서 내가 원하는 범위만큼의 문자가 string변수에 담아집니다.

 

자 그럼 코드 보시죠

 

소스코드

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

int main(){
    string str;
    string bomb;
    
    cin >> str >> bomb;
    
    vector<char> stack;
    
    int strlen = str.length();
    for(int i = 0 ; i < strlen ; i++){
        stack.push_back(str[i]);
        //validate
        if(stack.size() >= bomb.length()){
            string candidate(stack.end()-bomb.length(), stack.end());
            if(candidate == bomb){
                int bomblen = bomb.length();
                for(int j = 0 ; j < bomblen ; j++)
                    stack.pop_back();
            }
        }
    }
    
    if(stack.empty()){
        cout << "FRULA";
    }else{
        string result(stack.begin(), stack.end());
        cout << result;
    }
    
    return 0;
}

 

그리고 시간초과 떴지만 결과는 나오는 Swift 코드

import Foundation

var str:String = readLine() ?? ""
var bomb:String = readLine() ?? ""

while(true){
    if str.isEmpty {
        print("FRULA")
        break
    }
    let range = str.range(of: bomb)
    if range == nil { break }
    else {
        str.replaceSubrange(range!, with: "")
    }
}

print(str)