문자열 폭발 
https://www.acmicpc.net/problem/9935
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 128 MB | 97727 | 27262 | 19242 | 27.023% |
문제
상근이는 문자열에 폭발 문자열을 심어 놓았다.
폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다.
남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. - 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다.
남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
예제 입력 1
mirkovC4nizCC44 C4
예제 출력 1
mirkovniz
예제 입력 2
12ab112ab2ab 12ab
예제 출력 2
FRULA
출처
Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #5 3번
알고리즘 분류
통과된 코드
#include <iostream> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string S, C; cin >> S >> C; string Res; for (char ch : S) { Res.push_back(ch); // Res의 마지막 부분이 c와 같은지 확인 if (Res.size() >= C.size() && Res.substr(Res.size() - C.size()) == C) { // 문자열에서 폭발 문자열 제거 Res.erase(Res.size() - C.size()); } } cout << (Res.empty() ? "FRULA" : Res); return 0; }
예시 ch = 'm'
: Res = "m"
ch = 'i'
: Res = "mi"
ch = 'r'
: Res = "mir"
ch = 'k'
: Res = "mirk"
ch = 'o'
: Res = "mirko"
ch = 'v'
: Res = "mirkov"
ch = 'C'
: Res = "mirkovC"
ch = '4'
: Res = "mirkovC4"
ch = 'n'
: Res = "mirkovn"
ch = 'i'
: Res = "mirkovni"
ch = 'z'
: Res = "mirkoviz"
ch = 'C'
: Res = "mirkovnizC"
ch = 'C'
: Res = "mirkovnizCC"
ch = '4'
: Res = "mirkovnizCC4"
ch = '4'
: Res = "mirkovnizC4"
Res = “mirkovniz”