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보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모
www.acmicpc.net
흐름
선생님 코드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개만 지워짐
[C++] string::erase - 특정 문자열 삭제 함수
[C++] string::erase *개인적인 공부 내용을 기록하는 용도로 작성한 글 이기에 잘못된 내용을 포함하고 있을 수 있습니다. _contents #1 string::erase #2 example #2.1 sequnce _ 특정 길이 만큼의 문자열 제거 #2.2 c
novlog.tistory.com
<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;
}