420 words
2 minutes
[BOJ] 문자열 폭발
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 128MB | (1<= N <= 1’000’000, 1 <= Bomb <= 36) | Stack(스택) |
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
이 문제는 사실 전형적인 Stack 문제여서 생각을 많이 하진 않았던 것 같다. 그냥 시간복잡도 보고서 음 괜찮네하고 짰는데 AC를 맞았다.
정답 코드
#include <iostream>
#include <vector>
using namespace std;
string N, bomb;
int main(){
cin >> N;
cin >> bomb;
vector<char> stack;
int length = (int) bomb.size();
for(int i = 0; i < N.size(); i++){
stack.push_back(N[i]);
if(stack.size() >= length){
bool check = false;
for(int j = 0; j < length; j++){
if(bomb[length - j - 1] == stack[stack.size() - j - 1]) continue;
check = true;
break;
}
if(check) continue;
for(int j = 0; j < length; j++) stack.pop_back();
}
}
if(stack.empty()) cout << "FRULA";
else{
for(int i = 0; i < stack.size(); i++) cout << stack[i];
}
return 0;
}
[BOJ] 문자열 폭발
https://compy07.github.io/Blog/posts/boj/9935/