이번에는 백준 9935번 문자열 폭발 문제를 풀어보았습니다.
처음에는 문자열에서 폭발 문자열을 계속 찾아 제거하는 방식으로 구현해보았습니다.
하지만 문자열을 계속 분리하고 다시 합치는 과정이 반복되기 때문에 최악의 경우 시간 초과가 발생했습니다.
이후에는 문자열을 앞에서부터 하나씩 확인하면서 현재까지 만들어진 문자열의 끝부분만 검사하는 방식으로 다시 구현하였습니다.
문제 설명
문자열과 폭발 문자열이 주어집니다.
문자열 안에 폭발 문자열이 존재하면 해당 문자열이 제거되고, 남은 문자열이 다시 이어집니다.
이 과정을 폭발 문자열이 더 이상 존재하지 않을 때까지 반복한 뒤 남은 문자열을 출력하는 문제입니다.
풀이 아이디어
V1
처음에는 문자열을 split하여 폭발 문자열을 제거한 뒤 다시 이어 붙이는 방식으로 구현하였습니다.
하지만 폭발이 발생할 때마다 문자열 전체를 다시 탐색해야 했기 때문에 최악의 경우 시간 초과가 발생하였습니다.
V2
문자열을 앞에서부터 하나씩 읽으며 새로운 문자열 ret을 만들어 갔습니다.
문자를 하나 추가할 때마다 ret의 마지막 부분이 폭발 문자열과 같은지만 확인하였습니다.
같다면 즉시 제거하였습니다.
이 과정을 반복하면 새롭게 이어지는 문자열에서 발생하는 폭발도 자연스럽게 처리할 수 있었습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
vector<string> split(const string &s, string delim) {
vector<string> tokens;
auto beg = 0;
auto end = s.find(delim);
while(end != string::npos) {
tokens.push_back(s.substr(beg,end-beg));
beg = end+delim.size();
end = s.find(delim, beg);
}
tokens.push_back(s.substr(beg));
return tokens;
}
int main() {
string str, bomb;
cin >> str >> bomb;
while(true) {
vector<string> splitted = split(str, bomb);
string temp = "";
for (string s : splitted) {
temp += s;
}
if (temp == "" || temp == str) {
str = temp;
break;
}
str = temp;
}
if (str == "")
cout << "FRULA\n";
else
cout << str << '\n';
return 0;
}V1 풀이 흐름
- 문자열을 폭발 문자열 기준으로 분리합니다.
- 분리된 문자열을 다시 이어 붙입니다.
- 문자열이 더 이상 변하지 않을 때까지 반복합니다.
- 최종 문자열을 출력합니다.
V1 구현 포인트
1. split을 이용한 제거
폭발 문자열을 기준으로 문자열을 분리하였습니다.
vector<string> splitted = split(str, bomb);분리된 문자열에는 폭발 문자열이 제거된 상태가 됩니다.
2. 문자열 다시 합치기
분리된 문자열을 다시 이어 붙였습니다.
string temp = "";
for (string s : splitted) {
temp += s;
}이렇게 새 문자열을 만들어 다음 탐색을 진행하였습니다.
3. 시간 초과
폭발이 한 번 발생할 때마다 문자열 전체를 다시 탐색하게 됩니다.
while(true)가 반복되므로 최악의 경우 매우 많은 문자열 복사가 발생하여 시간 초과가 발생하였습니다.
V2 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
string str, bomb;
cin >> str >> bomb;
int bomb_size = bomb.size();
string ret = "";
for (int i=0; i<str.size(); i++) {
ret.push_back(str[i]);
if (ret.size() >= bomb_size) {
bool flag = true;
for (int j=0; j<bomb_size; j++) {
if (ret[ret.size()-bomb_size+j] != bomb[j]) {
flag = false;
break;
}
}
if (flag) {
for (int j=0; j<bomb_size; j++) {
ret.pop_back();
}
}
}
}
if (ret == "")
cout << "FRULA\n";
else
cout << ret << '\n';
return 0;
}V2 풀이 흐름
- 문자열을 앞에서부터 하나씩 읽습니다.
- 현재 문자를
ret뒤에 추가합니다. ret의 마지막 부분이 폭발 문자열인지 확인합니다.- 같다면 해당 부분을 제거합니다.
- 문자열 끝까지 반복합니다.
- 결과를 출력합니다.
구현 포인트
1. 새로운 문자열 생성
현재까지 남아 있는 문자열을 ret에 저장하였습니다.
string ret = "";문자를 하나씩 추가하며 결과 문자열을 만들어 갔습니다.
ret.push_back(str[i]);2. 마지막 부분만 비교
현재 문자열의 길이가 폭발 문자열 이상일 때만 비교를 수행하였습니다.
if (ret.size() >= bomb_size)문자열 전체를 다시 탐색하지 않고 끝부분만 검사하였습니다.
3. 폭발 문자열 확인
ret의 마지막 bomb_size개의 문자만 비교하였습니다.
for (int j=0; j<bomb_size; j++) {
if (ret[ret.size()-bomb_size+j] != bomb[j]) {
flag = false;
break;
}
}끝부분이 폭발 문자열과 같다면 제거를 수행하였습니다.
4. 폭발 처리
폭발 문자열과 일치하면 마지막 문자들을 제거하였습니다.
for (int j=0; j<bomb_size; j++) {
ret.pop_back();
}이후 새롭게 이어진 문자열도 다음 반복에서 다시 검사되므로 연쇄 폭발도 자연스럽게 처리됩니다.
5. 시간복잡도 개선
V1은 문자열을 계속 분리하고 다시 합쳐야 했기 때문에 반복적으로 문자열 전체를 탐색하였습니다.
반면 V2는 문자열을 한 번만 순회하면서 최대 폭발 문자열 길이(36)만큼만 비교하므로,
시간복잡도는 O(N × 폭발 문자열 길이)가 되어 충분히 제한 안에서 해결할 수 있었습니다.
