📖 백준 9935번 : https://www.acmicpc.net/problem/9935
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 128 MB |
문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
풀이
문제에서 주어진대로 단순하게 구현하면 입력이 1,000,000이기 때문에 시간 초과를 할 가능성이 높다. 처음 접근할 때는 폭발 문자열들을 전부 찾고 지운 다음에 다시 전부 찾고 지우고를 반복하는 방식으로 구현했다. 이 방식으로 풀면 최악의 경우 1,000,000 * 500,000 이기 때문에 당연하게 시간 제한을 넘기지 못했다.
- 최악의 경우
aaaa...aaaabbbb...bbbb <- 주어진 문자열의 길이가 1,000,000인 경우
ab
이 문제의 분류가 스택인 것을 알고 다른 방법으로 접근했다. 문자열을 하나씩 스택에 채워가면서 스택의 크기가 폭발 문자열의 크기와 같거나 더 커졌을 때, 뒤에서부터 같은지 확인하고 지운다. 그리고 다시 하나씩 스택에 채워가면서 뒤에서 부터 같은지를 체크하는 것을 N번 반복하면 한번의 탐색으로 문자열 폭발을 만족시킬 수 있다.
EX)
12ab112ab2ab
12ab
T="1"
T="12"
T="12a"
T="12ab" <- 스택 T와 폭발 문자열의 크기가 같거나 더 커진 경우, 폭발 문자열과 같아서 지움
T="1"
T="11"
T="112"
T="112a" <- 크기가 같거나 더 크니까 체크, 하지만 폭발 문자열과 달라서 지우지 않음
T="112ab" <- 크기가 같거나 더 크니까 체크, 폭발 문자열과 같아서 지움
T="12"
T="12a"
T="12ab" <- 크기가 같거나 더 크니까 체크, 폭발 문자열과 같아서 지움
T=""
끝
이런 방식으로 구현하면 O(N)으로 문제를 풀 수 있다. 나는 std::string을 적절히 활용해서 구현을 간단하게 했다. find()의 시작점을 스택.size() - 폭발문자열.size()로 해서 뒤에서 체크하게 만들고, 이 값이 string::npos일 때는 값을 찾지 못했다는 뜻이므로 같지 않을 때만 체크해서 값을 지운다. erase()의 시작점을 find()로 찾은 값으로 지정하고 폭발문자열의 크기만큼 지웠다.
코드
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string word, bomb;
string ans = "";//스택처럼 사용
cin >> word >> bomb;
for (int i = 0; i < word.size(); i++) {
ans += word[i];//하나씩 붙임, 스택의 push와 같다
if (ans.size() >= bomb.size()) {
int del_index = ans.find(bomb, ans.size() - bomb.size());//뒤에서 찾기
if (del_index != string::npos) ans.erase(del_index, bomb.size());//찾은 값을 바탕으로 삭제
}
}
if (ans.size() == 0) cout << "FRULA";
else cout << ans;
return 0;
}
