[백준] 9935-문자열 폭발(C++)

어려웠습니다...

 

 

우선 첫번째로 고려하셔야 하는게 "문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다." 입니다

일반적인 방법으로 문제에 접근하면 "어 그냥 반복해서 문자열을 지워주다가 지울게 없으면 출력하면 되겠네" 겠죠.

 

이때, 최악의 경우 O(n^2)입니다. (n X n/2) 

시간제한범위를 한참 넘습니다. (1억번의 연산당 1초정도입니다.)

1000000 X 1000000/2 = 500000000000 > 200000000

 

 

따라서, 다른방법을 생각해보아야 합니다. 

스택을 사용해야합니다. 

1. 모든 문자열을 스택에 넣는다. 

2. 넣으면서 폭발문자열의 끝 문자와 같다면 스택을 검사합니다.

3. 폭발문자열이 있는지 확인하고, 있다면 해당문자열을 지워줍니다. 

 

 

위 의 방식으로 O(n) 번만에 값을 찾을 수 있습니다.  

 

 

 

 

 

 

두번째로 고려하셔야 할게 있습니다. 

 

저는 string의 erase함수를 사용하며 데이터를 지우면서 결과값을 도출했는데, 45%에서 시간초과가 났습니다. 

1. C의 strlen
2. C++의 string.erase
3. Java의 String.replaceAll
4. Python의 str.replace, str.find, list.pop(i) etc

굳이 내장함수가 아니더라도 단순히 문자열의 중간을 한 번 지울 때마다 거의 무조건 O(N)이 걸립니다. 즉 지우는 행위를 하면 안됩니다. 

 

 

 

 

 

곰곰히 생각해보니까 해당 스택자체가 결과값이더군요... ( 연결되는 모든 폭발 문자열을 지운 문자열 그자체..)

이거를 늦게 알아서, 고생한 문제 였습니다. 

 

#include <iostream>
#include <string>
using namespace std;

string basic,bomb;
char result[1000001];
int  result_cur = 0;
int main() {
	char lastword;
	cin >> basic;
	cin >> bomb;
	lastword = bomb[bomb.size() - 1];

	for (int i = 0; i < basic.size(); i++) {
		result[result_cur++] = basic[i];
	

		if (basic[i] == lastword) //마지막 문자열과 다르면 스택에 담습니다.
		 { 
			
				bool jud = true;
				for (int j = bomb.size() - 1; j >= 0; j--)
				{
					if (bomb[j] != result[result_cur - 1 - (bomb.size() - 1) + j]) { // 스택의 가장위쪽부터 한칸씩 내려오면서 검사
						jud = false; //즉 해당문자열이 아니면 false
						break;
					}
				}
				if (jud == false) {
					continue;
				}
				else { 
								
					for (int j = 0; j < bomb.size(); j++) {
						result_cur--;				
					}
				}	
		}
	}
	if (result_cur==0)
		cout << "FRULA" << '\n';
	else {
		
		for (int i = 0; i < result_cur; i++) {
			cout << result[i];
		}
		cout << '\n';
	}
}

 

 

result 는 스택, 결과값 입니다. 

 

 

 

 

 

for (int j = bomb.size() - 1; j >= 0; j--)
				{
					if (bomb[j] != result[result_cur - 1 - (bomb.size() - 1) + j]) { // 스택의 가장위쪽부터 한칸씩 내려오면서 검사
						jud = false; //즉 해당문자열이 아니면 false
						break;
					}
				}

3. 폭발문자열이 있는지 확인하고,

 

for (int j = 0; j < bomb.size(); j++) {
						result_cur--;				
					}

 

있다면 해당문자열을 지워줍니다. (스택에서 단순히 커서를 내려줌으로써 지울 수 있겠죠.)

 

 

화이팅:)