💎 문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
💎 입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
💎 출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
💎 풀이 방법
처음에 보고 문자열의 뒷부분부터 검사를 해서 스택구조로 풀어야할 것 같고 폭탄 문자열과 스택 문자열의 맨 뒤가 같으면 앞 문자열을 차례대로 비교하면서 빼줘야겠다,,,!! 라고 바로 생각은 들었는데 스택으로 풀려고 하다보니 pop해주는 과정 때문에 어떡하지라고 오히려 조금 헤맸던 문제였다,,,,
따라서 오히려 간단하게 문자열만을 이용하되 문자열 자체를 스택으로 생각하고 이에 대한 특정 위치 문자열을 접근하는 방식으로 푸는 것이 오히려 효율적이었다. 스택이라는 개념을 알아두되 굳이 스택 STL라이브러리를 이용하지말고 문자열의 구조를 스택이라고 생각하도록 접근도 해보자!!!
따라서 굉장히 간단하게 풀 수 있었다!! 주어진 문자열의 앞부분부터 차례대로 결과 문자열에 넣어주면서 이 결과 문자열의 맨 뒤 문자가 폭탄의 맨 뒤 문자와 일치하면 검사를 시작한다.
for(int i = 0;i < word.length();i++){
result.push_back(word[i]);
if(bomb[bomb.size() - 1] == result.back()){
bool check = true;
for(int j = 1;j <= bomb.size();j++){
if(result[result.size()- j] != bomb[bomb.size()- j])
check = false;
}
if(check){
for(int j = 0; j < bomb.size();j++){
result.pop_back();
}
}
}
}반복문을 진행하면서 폭탄의 맨 뒤 문자가 발견되면 bool변수를 이용하여 결과 문자열에 넣어줬던 문자를 뒤에서 부터 검사하고 폭탄과 일치하는 문자열을 발견 완료한다면 bool 변수가 true일 때 이를 결과 문자열의 뒤 부분을 pop해준다. 이러한 구조는 스택인 것을 확인할 수 있었다!!!
💎 전체 코드
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(int argc, const char * argv[]) {
string word;
string bomb;
cin >> word >> bomb;
string result = "";
for(int i = 0;i < word.length();i++){
result.push_back(word[i]);
if(bomb[bomb.size() - 1] == result.back()){
bool check = true;
for(int j = 1;j <= bomb.size();j++){
if(result[result.size()- j] != bomb[bomb.size()- j])
check = false;
}
if(check){
for(int j = 0; j < bomb.size();j++){
result.pop_back();
}
}
}
}
if(result == "")
cout << "FRULA" << "\n";
else
cout << result << "\n";
return 0;
}💎 고민
항상 문제를 읽고나서 어떻게 풀지 감을 잡았다면 그것을 활용할 수 있는 STL 클래스를 활용하는 것에 중점을 두었었는데, 오히려 그런 식으로 풀려다보니 '어떻게 특정 인덱스에 위치한 문자열에 접근하지,,,'라는 벽을 만났던 것 같다. 알고리즘 개념을 활용하되 이를 반드시 STL 클래스를 이용하는 습관은 좀 줄이고 알고리즘 개념을 이용하여 코드를 짜는 습관을 들이도록 하자,,,
화팅!! 인제 곧 중간고사 기간
