완전탐색으로는 N * M time이 걸리는 문제를
스택을 사용해서 N time으로 바꾸어 주는 문제이다.
문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
풀이는 간단하다.
주어진 문자열에 대한 폭발 문자열의 정보를 stack을 하나 만들어서 넣어주고, 이것을 체크해주는 방식으로 문제를 풀 면 된다.
기본적으로 입력받은 문자열의 (첫째 줄에 입력받은 문자열) 모든 원소를 탐색하면서, 경우의 수를 나눈다.
- 입력받은 문자열의 원소 c가 폭발문자열에 있지 않은 경우.
- 입력받은 문자열의 원소 c가 폭발문자열에 있으면서, 폭발 문자열의 0번째 원소과 같은 경우.
- 입력받은 문자열의 원소 c가 폭발문자열에 있으면서, 기존에 체크한 인덱스에 해당하는 폭발문자열의 원소와 같은 경우.
아마 1, 2번은 문장을 보고 직관적으로 이해할 수 있지만, 3번이 이해가 잘 되지 않을 것이다.
3번을 간단히 말하면, 입력받은 문자열의 원소 c가 폭발문자열의 원소 중 하나이고, 폭발문자열의 0번째 인덱스 부터 쭉 이어져서 현재 idx번째 인덱스에 해당할 경우이다.
예를들어 abcdefgh라는 문자열이 주어지고, def라는 폭발 문자열이 주어졌을때
a, b, c는 폭발 문자열의 원소가 아니기 때문에 1번 조건으로 넘어가게 되고,
d는 2번 조건에 해당하기 때문에 넘어가게 된다. 그리고 e로 가게 되는데 e는 이전의 원소(원소들) 가 폭발 문자열을 충족 하기 때문에 3번 조건에 해당하게 된다.
이렇게 f도 3번 조건을 충족하게 되고, 그러므로 def가 문자열에서 빠지게 되는 방식이다.
이를 구현한다면
for(auto c : s){
if(c == bomb[idx]){
index.push_back((idx));
ans.push_back(c);
idx += 1;
if(index.back() == bomb.size()-1){
for(int i=0; i<bomb.size(); i++){
index.pop_back();
ans.pop_back();
}
if(index.empty()){
idx = 0;
}else{
idx = index[index.size()-1]+1;
}
}
}else{
if(c == bomb[0]){
index.push_back(0);
ans.push_back(c);
idx = 1;
}else{
idx = 0;
ans.push_back(c);
index.push_back(-1);
}
}
}이런 형태가 된다.
처음부터 설명을 하자면
if(c == bomb[idx]){
index.push_back((idx));
ans.push_back(c);
idx += 1;
if(index.back() == bomb.size()-1){
for(int i=0; i<bomb.size(); i++){
index.pop_back();
ans.pop_back();
}
if(index.empty()){
idx = 0;
}else{
idx = index[index.size()-1]+1;
}
}
}이 구문이 3번 조건에 해당하고,
else{
if(c == bomb[0]){
index.push_back(0);
ans.push_back(c);
idx = 1;
}else{
idx = 0;
ans.push_back(c);
index.push_back(-1);
}
}이 구문이 1, 2번조건에 해당하게 된다.
3번 조건을 해결하기 위해서는 인덱스 정보를 저장하는 스택을 하나 사용해 주어야 한다.
else{
idx = 0;
ans.push_back(c);
index.push_back(-1);
}이렇게 1번 조건에 해당하는 경우에는 index스택에 -1을 넣어주게 된다. 왜냐하면 폭발할 가능성이 없기 때문에.
if(c == bomb[0]){
index.push_back(0);
ans.push_back(c);
idx = 1;
}2번 조건에 해당하는 경우에는 index 스택에 0을 넣어주게 된다.
2번조건과 3번 조건을 같이 해줄 수도 있지만, 따로 나눈 이유는 문자열이 폭발 하려면 항상 폭발문자열의 0번째 원소부터 나와야 하기 때문이다.
if(c == bomb[idx]){
index.push_back((idx));
ans.push_back(c);
idx += 1;
if(index.back() == bomb.size()-1){
for(int i=0; i<bomb.size(); i++){
index.pop_back();
ans.pop_back();
}
if(index.empty()){
idx = 0;
}else{
idx = index[index.size()-1]+1;
}
}
}이 부분이 3번 조건에 해당하는 부분이자, 문자열을 폭발시키는 구문이다.
index.push_back((idx));
ans.push_back(c);
idx += 1;이 부분은 2번 구문과 거의 비슷하다. index stack에 현재 idx정보를 넣어주고, 이 idx + 1를 해준다.
중요한 것은
if(index.back() == bomb.size()-1){
for(int i=0; i<bomb.size(); i++){
index.pop_back();
ans.pop_back();
}
if(index.empty()){
idx = 0;
}else{
idx = index[index.size()-1]+1;
}
}이 부분이다.
index.back()(stack의 top을 의미한다.) 이 bomb.size()-1과 같으면, 폭발문자열이 끊기지 않고 다 나왔단 의미이다. 그러므로 폭발문자열의 사이즈 만큼 ans string에서 이를 빼주게 된다.
