


백준 9935 문자열 폭발
백준 9935 문자열 폭발
2022년 11월 27일
2022년 11월 27일
cpp, 문자열, 스택
문제
문제
풀이
풀이
해당 문제는 kmp를 이용할 경우, 100만개의 문자열에 대해 매번 문자열 폭발이 일어난다면 시간복잡도 o(s*s)으로 시간초과가 난다.
하지만 스택을 이용해서 폭발 문자열에 해당하지 않는 문자열만 담는다면 o(s)에 해결이 가능하다.
코드
코드
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string s, bomb;
stack<char> ans; // 폭발에 해당하지 않는 문자만 담는다.
stack<char> tmp; // 폭발 문자열 검증용 임시 스택
cin >> s >> bomb;
int index;
for (char e : s)
{
index = bomb.size() - 1;
ans.push(e);
while (!ans.empty() && ans.top() == bomb[index])
{
tmp.push(e);
ans.pop(); // 폭발 문자열과 일치하는 문자들을 임시 스택에 보관
if (index == 0)
{
// index가 0에 도달하면 폭발 문자열 검증 성공
while(!tmp.empty()) tmp.pop();
break;
}
--index;
}
while (!tmp.empty())
{
// 폭발 문자열 검증에 실패할 경우 tmp에 보관한 값들을 다시 넣어줌.
ans.push(tmp.top());
tmp.pop();
}
}
if (ans.empty())
cout << "FRULA";
else
{
// ans에 보관한 값들을 거꾸로 출력하면 완료.
while (!ans.empty())
{
tmp.push(ans.top()); // tmp 스택 재활용
ans.pop();
}
while (!tmp.empty())
{
cout << tmp.top();
tmp.pop();
}
}
}
결과
결과

Copyright © 2024 Hyunghoon Kim