9935번: 문자열 폭발

문자열 폭발 

성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초 (추가 시간 없음)

128 MB

55350

13872

9732

24.867%

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1 복사

mirkovC4nizCC44
C4

예제 출력 1 복사

mirkovniz

예제 입력 2 복사

12ab112ab2ab
12ab

예제 출력 2 복사

FRULA

 

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

9935번: 문자열 폭발

 

 

흐름

선생님 코드1 - 폭발 문자열 크기만큼 조사

#include <bits/stdc++.h>
using namespace std;

string S,T,ret;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> S >> T;
    //2. 폭발 문자열 지우기
    for(char a:S){
        ret += a;
        //T 길이만큼 조사한다. T가 존재하면 지운다.
        if(ret.size()>=T.size() && ret.substr(ret.size()-T.size()) == T){
            ret.erase(ret.end()-T.size(), ret.end());
        }
    }
    //3. 문자열 출력하기
    if(!ret.size()) cout<<"FRULA" << "\n";
    else cout << ret <<"\n";

    return 0;
}

 

ret.size()와 ret.end()를 원하는대로 막 바꾸어 사용하면 오류가 났기때문에 ret.size()로 통일하여 코드를 재작성했다.

 

<string>
erase(시작인덱스, 삭제할 문자열 갯수) =>size() 
erase[시작 반복자, 끝 반복자) => .begin(), .end() //끝반복자 안적으면 글자 1개만 지워짐

 

 

자세한 내용: https://novlog.tistory.com/entry/C-stringerase-%ED%8A%B9%EC%A0%95-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%82%AD%EC%A0%9C-%ED%95%A8%EC%88%98

[C++] string::erase - 특정 문자열 삭제 함수

 

<string>
substr(시작인덱스, 추출글자수); //추출 글자수 생략되면 끝까지

 

size()로 통일한 코드

#include <bits/stdc++.h>
using namespace std;

string S, T,ret;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> S >> T;
    //2. 폭발문자열 제거하기
    for(char c:S){
        ret += c;
        if(ret.size()>=T.size() && ret.substr(ret.size()-T.size())==T){
            ret.erase(ret.size()-T.size(),T.size());
        }
    }
    //3. 출력하기
    if(!ret.size()) cout << "FRULA" << "\n";
    else cout << ret;
}

 

선생님 코드 2 - 스택 이용

#include <bits/stdc++.h>
using namespace std;

string S,T, answer;
stack<char> stk;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 문자열 입력받기
    cin >> S >> T;
    //2. 폭발 문자열 제거하기
    for(char a:S){
        stk.push(a);
        if(stk.size()>=T.size() && stk.top()==T[T.size()-1]){ //스택에 들어온 문자가 폭발 문자열의 마지막 글자이면
            string ss="";
            for(char c:T){ //T크기만큼 pop하기
                ss+=stk.top(); stk.pop();
            }
            reverse(ss.begin(), ss.end());
            if(ss != T){ //폭발 문자열이 아니면
                for(char c:ss) stk.push(c); //원상복구하기
            }
        }
    }
    //3. 정답 출력하기
    while(!stk.empty()){
        answer += stk.top(); stk.pop();
    }
    reverse(answer.begin(), answer.end());
    if(answer.size()==0) cout << "FRULA";
    else cout << answer;

}