[G4] 백준 9935번 문자열 폭발 C++ 문자열, 스택

리뷰

 

https://www.acmicpc.net/problem/9935

알고리즘 분류를 보지 않고 풀었을 때는 string STL의 find + replace를 사용했었다.

결과는 46%에서 멈추더니 시간 초과를 출력해냈다. replace메서드가 시간을 많이 잡아먹는다 하더라

결국 스택으로 돌리고 구현을 했더니 이번엔 stack.size()가 문제였다.

for문에 size를 사용할땐 왠만하면 정수형으로 치환한 후에 사용하도록 하자..

 

전역 변수

• s, b : 탐색을 진행할 문자열 s, 폭발을 일으킬 문자열 b
• n, m : 문자열 s의 길이 n, 문자열 b의 길이 m
• stack : 스택으로 사용할 문자형 벡터

 

함수

1. chk

bool chk()

 

현재 스택에 폭발할 문자열이 있는지 여부를 체크하는 함수

1. idx는 0, len은 스택의 크기로 설정해 준다.
2. 스택의 뒤에서부터 m만큼 탐색을 진행한다.
3. 만약 b가 존재한다면 true를 반환하고, b와 하나라도 틀릴 경우 flase를 반환한다.

 

2. bomb

void bomb()

 

chk함수로 부터 bool형을 리턴 받아 폭파시킬지 말지를 결정하는 함수

1. 스택의 크기가 m이상이고, 스택의 끝이 폭발 문자열의 시작 문자와 같다면 반복한다.
2. chk함수의 리턴값이 true라면 m개만큼 스택의 뒤에서 문자를 제거해준다.
3. 만약 chk함수의 리턴값이 false라면 break 처리해준다.

 

문제풀이

1. s, b를 입력받고, b를 reverse처리해 준다.
2. n, m에 s, b의 크기를 초기화 해준다.
3. n번의 반복문을 돌리며 bomb함수를 실행한 후에 스택에 i번째 문자를 추가해 준다.
4. 반복문이 종료되어도 남아있는 케이스가 있을 수 있으니 bomb을 한번 더 실행해 준다.
5. 만약 스택이 비어있다면 FRULA를 출력해 준다.
6. 스택이 비어있지 않다면 스택의 앞부터 문자를 출력해 준다.

 

참고 사항

스택을 사용할 경우 폭발 문자열의 뒤부터 탐색해 주어야 하므로 b를 reverse로 전처리해 주었다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

string s, b;
int n, m;
vector<char> stack;

bool chk() {
	int idx = 0;
	int len = stack.size();
	for (int i = len - 1; i >= len - m; i--) {
		if (stack[i] != b[idx++]) return false;
	}
	
	return true;
}

void bomb() {
	while (stack.size() >= m && stack.back() == b[0]) {
		if (chk()) {
			int temp = m;
			while (temp--) stack.pop_back();
		}
		else break;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s >> b;

	reverse(b.begin(), b.end());
	n = s.size(), m = b.size();
	for (int i = 0; i < n; i++) {
		bomb();
		stack.push_back(s[i]);
	}
	bomb();

	if (stack.empty()) cout << "FRULA";
	else for (const char& ch : stack) cout << ch;
}