9 min to read
PS 풀이 - BOJ 9935 문자열 폭발
백준 9935번 문제 풀이 포스팅
개요
BOJ 9935 문자열 폭발 썸네일에 나와있듯, 골드 4 문제이며, solved.ac 기준으로, 클래스 4에 수록되어 있는 문제입니다. 제가 생각해서 푼 방식과, 제가 푼 방식보다, 메모리/시간 모두 아낀 방법 두가지 모두 이 글에서 소개 해 보려고 합니다.
문제 설명
문자열 안에 “폭발 문자열” 이라는 것을 도입합니다. 폭발 문자열이 동작하는 조건은 다음과 같습니다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하여 사라지게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
출력으로 폭발이 모두 끝났을때의 최종 문자열을 출력하는 문제입니다. 단, 폭발이 끝나고 남은 문자열의 길이가 0이라면, FRULA를 대신 출력합니다.
그리고 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않습니다.
문제 제한
문자열의 길이는 최소 1, 최대 1,000,000 입니다. 폭발 문자열의 길이는 1보다 크고 36보다 작습니다. 시간제한은 2초고, 메모리 제한은 128MB 입니다.
단순하게는 풀 수 없다
이 문제는 문제의 설명을 그대로 구현하는 시뮬레이션으로 풀 수 있는 문제인지 우선 알아봅시다. 문자열을 검색하고, 특정 문자열 패턴이 나오면, 문자열 가운데에서 해당 패턴을 제거하고, 다시 검색하고…. 이 과정을 반복하는게 시간 제한이나 메모리 제한에 걸리지 않을지 한번 알아봅시다.
이 과정의 시간 복잡도를 대강 알아봅시다.
- 문자열 검색 : $O(N)$ N은 문자열의 길이
- 문자열 제거 후 문자열 봉합 : $O(N)$ N은 문자열의 길이
최악의 상황으로, 폭발 문자열이 ‘ab’이고, 주어진 문자열이 ‘aaaaa…bbbbb…‘(a 와 b의 개수가 각각 500,000개) 라고 합시다. 검색/제거 과정을 총 500,000 회 반복해야 하고, 여기에 필요한 연산의 수는 초항이 0이고, 공차가 2, 막항이 500,000 인 등차수열의 합이므로, 계산해보면, 2억이 훌쩍 넘어가는 2500억 입니다. 이정도면 죽었다 깨어나도, 시간 내에 풀 수 없음을 알 수 있습니다. 다른 방법을 생각해 봅시다.
스택을 이용한다면?
단순하게 풀 수 없음을 알아내고, 이 문제를 다시 봤을 때, 떠오른 문제가 있습니다. 괄호의 쌍을 판별하는 BOJ 9012 괄호 문제인데요, 이 문제에서는 ‘(‘ 와, ‘)’로 된 문자열이 주어지고, 그 문자열의 괄호의 쌍이 올바르게 되어 있는지를 확인하는 문제입니다. 이 문제를 풀 때는, 스택을 이용해서, 괄호의 쌍이 올바르게 되어 있는지를 확인했는데, 이번 문제에서, 폭탄 문자열을 판별하는데, 괄호 문제를 풀 때 처럼 스택을 쓰면 좋겠다라는 생각이 들었습니다. 위의 괄호 문제는, 어떻게 보면, 주어지는 문자열이 ‘(‘, ‘)’로만 이루어 져있고, 폭발 문자열이 ‘()’ 일 때, 폭발을 모두 마친 후, 남는게 있는지 없는지 확인하는 문제로 해석할 수 있으니까요.
이 생각이 든 후에, 위의 스택 문제와는 다르게, 폭발 문자열의 길이는 2보다 클 수 있으니까, 스택에 다른걸 넣어야 한다는 생각이 들었습니다. 문자열을 처음부터 쭉 훑다가, 폭발 문자열로 의심되는 문자열을 얼마만큼 읽었느냐에 대한 정보를 넣기로 생각을 정했습니다. 그렇게 한다면, 언젠가 다시 스택을 열어서 예전에 읽었던 폭발 문자열에 대한 정보와, 그 때 읽고있을 문자열의 정보를 합쳐서 폭발 문자열 여부를 확인할 수 있으니까요.
이제 어떻게 문제를 풀지 생각을 대강 정했으니, 코드를 적어보기로 했습니다.
처음 한 구현
저는 이 문제를 풀 때, 결과로 출력할 문자열을 추가로 하나 더 잡아서, 폭발에 영향을 받지 않는 문자열을 저장하기로 했습니다. 일단 코드를 이렇게 적어가고 있었습니다.
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(void){
string input,bomb,result = "";
cin >> input >> bomb;
stack<int> s;
for(int i = 0; i < input.size();){
int lastMatch = s.empty() ? 0 : s.top();
if(input[i] == bomb[0]){
for(int j = 0; j < bomb.size(); ++j){
if(input[i] != bomb[j]){
s.push(j);
break;
}
++i;
}
}
else if(input[i] == bomb[lastMatch]){
if(!s.empty()) s.pop();
for(int j = lastMatch; j < bomb.size();++j){
if(input[i] != bomb[j]){
s.push(j);
break;
}
++i;
}
}
else{
//이외의 문자열이 나왔을 때...
}
}
if(result.size() != 0)
cout << result;
else cout << "FRULA";
return 0;
}
폭발 문자열을 탐지하는 것에는 잘 작동했지만, 문제에 봉착했습니다. 폭발 문자열의 일부인줄 알고, 예전에 탐색했던 정보를 스택에 고이 담아놨었는데, 그 뒤에 폭발 문자열과 일체 상관없는 문자가 나와서, 결코 앞에 탐색했던 것들이 폭발 문자열이 될 수 없는 상황이라고 합시다. 이럴때는, 스택에 처음으로 넣은 원소부터 꺼내서, 예전에 탐색했던 문자열을 출력할 결과 문자열에 넣어야 하는 상황이 되었습니다. 근데, 스택의 특징 상, FIFO 연산을 하지 않고, FILO 연산을 하기 때문에, 두 연산 모두 지원하는 deque 자료구조를 이용해서 코드를 마무리했고, 일단 그 코드는 AC를 받긴 했습니다.
#include<iostream>
#include<string>
#include<deque>
using namespace std;
int main(void){
string input,bomb,result = "";
cin >> input >> bomb;
deque<int> s;
for(int i = 0; i < input.size();){
int lastMatch = s.empty() ? 0 : s.back();
if(input[i] == bomb[0]){
for(int j = 0; j < bomb.size(); ++j){
if(input[i] != bomb[j]){
s.push_back(j);
break;
}
++i;
}
}
else if(input[i] == bomb[lastMatch]){
if(!s.empty()) s.pop_back();
for(int j = lastMatch; j < bomb.size();++j){
if(input[i] != bomb[j]){
s.push_back(j);
break;
}
++i;
}
}
else{
while(!s.empty()){
result += bomb.substr(0,s.front());
s.pop_front();
}
result += input[i];
++i;
}
}
while(!s.empty()){
result += bomb.substr(0,s.front());
s.pop_front();
}
if(result.size() != 0)
cout << result;
else cout << "FRULA";
return 0;
}
위 코드는 작동은 합니다만, 중복되어 있는 부분이 있고, 이때까지 문제를 풀면서 쓸 일이 없었던 덱 자료구조까지 꺼냈는데, 다른 사람들은 어떻게 풀었나를 확인해 봤는데, 세상에나. 그사람들의 접근 방법은 훨씬 세련되고, 더 빠른 접근법 이었습니다.
더 세련된, 더 빠른 접근법
그 다른 접근법이란 이런것 이었습니다. 일단, 문자열을 훑을 때, 그게 뭐인지 상관없이, 결과 문자열에 넣습니다. 그리고, 폭발 문자열일 가능성이 있다면, 즉, 결과 문자열의 맨 위의 문자가, 폭발 문자열의 마지막 문자인지 체크하고, 폭발 문자열의 첫번째 원소까지 일치하는지 검사 한 다음, 완벽히 일치한다면, 결과 문자열에서 삭제 합니다. 문자열에서 직접 원소를 빼는것은 시간이 많이 들고, 결과를 단지 출력만 하면 되는 문제상황에서 이는 불필요 합니다. 결과 문자열의 유효한 정보가 담겨 있는 끝을 나타내는 변수 하나를 만들어서, 이를 관리하면 됩니다.
이를 구현한 것이 아래의 소스코드 입니다. 이 소스코드는 xowns9418님이 작성하신 코드 입니다.
#include<iostream>
#include<string.h>
using namespace std;
#define MAX_SIZE 1000001
char s[MAX_SIZE];
char bomp[40];
char result[MAX_SIZE];
int main(void) {
ios::sync_with_stdio(false);
cin >> s >> bomp;
int len_s = strlen(s);
int len_b = strlen(bomp);
int index=0;
bool flag;
for (int i = 0; i <= len_s; i++) {
result[index++] = s[i];
if (result[index-1] == bomp[len_b - 1]) {
flag = true;
for (int j = 0; j < len_b - 1; j++) {
if (result[index-len_b +j] != bomp[j]) {
flag = false;
break;
}
}
if (flag) {
index = index - len_b;
}
}
}
if (strlen(result) == 0) {
cout << "FRULA";
}
else {
cout << result;
}
}
여기에서 한발짝 더 나아갈 수도 있습니다. 결과 문자열의 끝을 나타내는 인덱스 변수는, 현재 문자열을 읽고 있는 인덱스보다 항상 같거나 작습니다. 이를 이용하면, 별도의 결과 문자열 변수를 만들지 않고, 문자열 변수 하나로도 문제를 해결할 수 있습니다. 항상 문자열의 끝만 읽는것을 고려할 때, 이 문제는 스택을 이용해서 푸는 문제로 생각을 할 수 있겠군요.
