본문 바로가기
알고리즘

[BOJ] 9935번: 문자열 폭발(C++)

by gibro 2021. 12. 12.

Problem


Solution

erase함수의 시간 복잡도는 O(N)이므로 erase함수를 사용하면 문제를 시간 내에 해결할 수 없다

 

1. 루프 문을 통해 문자열을 탐색하며 스택에 문자를 push 한다.

 

2. 만약 탐색한 문자가 폭발 문자열의 마지막 문자와 같으면 폭발 문자열의 길이만큼
스택에서 pop을 하여 폭발 문자열과 같은지 비교한다.

 

3. 스택에서 꺼낸 문자열과 폭발 문자열이 다르다면 꺼낸 문자들을 다시 스택에 넣는다.

 

4. 루프를 마치고 스택에 남아있는 문자열이 정답!!

 

#include <iostream>
#include <string>
#include <stack>
#include <vector>

using namespace std;

int main() {
	ios_base :: sync_with_stdio(false);
    	cin.tie(NULL);
    	cout.tie(NULL);

	string str, exp;
	
	cin>>str;
	cin>>exp;
	
	stack<char> s;

	int strlen = str.length();
	int explen = exp.length();

	for(int i=0; i<strlen; i++) {
		// 폭발 문자열의 마지막 문자와 같은지 비교한다
		if(str[i] == exp[explen-1]) {
			stack<char> tempStack;
			int j;
			for(j=1; j<explen; j++) {
				// 스택이 비어있을 경우 멈춘다
				if(s.empty()) break;

				char c = s.top();
				s.pop();
				tempStack.push(c);
				// 스택에서 꺼낸 숫자와 폭발 문자열의 숫자와 비교한다
				if(c != exp[explen - 1 - j]) break;
			}
			// 스택에서 꺼낸 문자 중 폭발 문자열과 다른 문자가 있다면
			if(j != explen){
				while(!tempStack.empty()){
					char c = tempStack.top();
					tempStack.pop();
					s.push(c);
				}
				// 마지막 문자도 넣는다
				s.push(str[i]);
			}

			continue;
		}

		s.push(str[i]);
	}

	vector<char> v;
	while(!s.empty()){
		char temp = s.top();
		s.pop();

		v.push_back(temp);
	}

	int veclen = v.size();
	string result;

	for(int i=veclen-1; i>=0; i--){
		result += v[i];
	}

	if(result == "") {
		cout<<"FRULA\n";
	}
	else{
		cout<<result<<"\n";
	}
}

Result

 

'알고리즘' 카테고리의 다른 글

[BOJ] 1806번: 부분합 (C++)  (0) 2022.01.04
[BOJ] 3176번: 도로 네트워크 (C++)  (0) 2021.12.18
[BOJ] 5052번: 전화번호 목록 (C++)  (0) 2021.12.16
[BOJ] 1701번: Cubeditor(C++)  (0) 2021.12.14

댓글