[C++] 백준(BOJ) - 9935 : 문자열 폭발
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
알고리즘
- 문자열
- 스택
풀이
- 문자열 길이 100만
- 이중 for문을 이용한 문제 풀이 (불가능) : 시간복잡도 초과
- substr과 erase를 활용하여 문자열 비교로 접근
- 문자열 비교 전에는 항상 사이즈 체크를 진행해야 한다
- erase 함수
iterator erase(const const_iterator _First, const const_iterator _Last) - substr 함수
substr(const size_type _Off = 0, const size_type _Count = npos)
- 스택을 이용한 문제풀이
- char형의 문자 하나씩 스택에 집어넣기
- 스택의 상단 부분과 폭발 문자열의 끝이 일치할 경우 스택에서 폭발 문자열 크기만큼 꺼내기
- Reverse (스택은 선입후출)
- 만약 꺼낸 문자열이 폭발 문자열과 일치하지 않으면 다시 스택에 삽입
코드 1 : 문자열
// BOJ-9935 : 문자열 폭발
#include<bits/stdc++.h>
using namespace std;
string a, b, res;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
for (char ch : a)
{
res += ch;
if (res.size() >= b.size() && res.substr(res.size() - b.size(), b.size()) == b)
{
res.erase(res.end() - b.size(), res.end());
}
}
if (!res.empty()) cout << res << '\n';
else cout << "FRULA\n";
return 0;
}
코드 2 : 스택
// BOJ-9935 : 문자열 폭발
#include<bits/stdc++.h>
using namespace std;
string a, b, res;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
stack<char> stk;
for (char ch : a)
{
stk.push(ch);
if (stk.size() >= b.size() && stk.top() == b[b.size() - 1])
{
string ss = "";
for (char i : b)
{
ss += stk.top();
stk.pop();
}
reverse(ss.begin(), ss.end());
if (b != ss)
{
for (char i : ss)
{
stk.push(i);
}
}
}
}
if (stk.empty()) cout << "FRULA\n";
else {
while (stk.size())
{
res += stk.top();
stk.pop();
}
reverse(res.begin(), res.end());
cout << res << "\n";
}
return 0;
}
평가
- 인덱스 에러 방지를 위해 문자열의 비교를 하기 전에 크기 비교를 항상 먼저하기
- 폭발, 짝짓기 문제는 스택과 연관 시켜 생각하기
