https://www.acmicpc.net/problem/9935
9935번: 문자열 폭발
문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난
www.acmicpc.net
문자열에서 특정 문자열(폭발 문자열)을 찾아 아예 없어질 때까지 반복해서 지워주는 문제입니다. 하지만 단순히 반복만 하면서 지울 경우 시간 초과를 받게 되는데요. 탐색 대상으로 들어오는 문자열의 길이를 N, 폭발 문자열의 길이를 M이라고 하겠습니다. 그럼 최악의 경우 \( O(N^2 M) \) 시간 복잡도가 나오면서 시간 초과를 받게 됩니다. 문자열 검색에 KMP(Knuth-Morris-Pratt) 알고리즘을 사용한다고 하더라도 \( O(N^2 + NM) \) 시간 복잡도가 나오면서 시간 초과를 피할 수는 없습니다.
이 문제를 해결하기 위해선 스택(stack)을 사용해야 합니다. 이를 이용하면 'CCC444' 같은 문자열에 대해서도 여러 번 반복해서 돌 필요 없이 딱 한 번 도는 것만으로도 없앨 수 있죠. 이때 시간 복잡도는 \( O(NM) \)이 되어 제한 시간 내에 통과할 수 있습니다.
전체적인 알고리즘은 다음과 같습니다.
- 탐색 대상으로 들어오는 문자열의 앞 글자부터 차례대로 스택에 넣음
- 1번 과정을 반복하면서 해당 문자가 폭탄 문자열의 맨 마지막 문자와 일치하는지 비교
- 만약 일치한다면 스택에 폭탄 문자열이 들어있는지 확인하고, 폭탄 문자열이 맞으면 그 부분을 제거
- 1 ~ 3번 과정이 모두 끝났으면 스택에 남아있는 문자열을 출력하고 종료
스택을 활용하는 아이디어를 떠올리는 것이 어려울 뿐, 알고리즘 자체는 크게 어려운 편은 아니었습니다. 저는 4번 과정을 좀 더 편하게 하기 위해서 인덱스(index) 접근이 가능한 덱(deque)을 사용했습니다.
#include <iostream>
#include <string>
#include <deque>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
deque<char> charList;
string mainStr, findStr;
cin >> mainStr >> findStr;
for (char ch : mainStr) {
bool checkFind = true;
// 스택(덱)에 문자를 하나씩 삽입
charList.push_back(ch);
// 폭발 문자열을 검색할 조건이 나올 때까지 대기
if (charList.size() < findStr.size() || ch != charList.back()) continue;
// 폭발 문자열 검색
for (size_t i = 0; i < findStr.size(); i++) {
if (charList[charList.size() - i - 1] != findStr[findStr.size() - i - 1]) {
checkFind = false;
break;
}
}
// 폭발 문자열이 맞다면 스택(덱)에서 제거
if (checkFind) {
for (size_t i = 0; i < findStr.size(); i++) charList.pop_back();
}
}
// 결과 출력
if (charList.size() == 0) {
cout << "FRULA";
}
else {
for (size_t i = 0; i < charList.size(); i++) {
cout << charList[i];
}
}
cout << "\n";
return 0;
}