[伯俊]9935:文字列爆発C++

9687 ワード
cpp 白駿 アルゴリズムの問題を解く テキストリンク

質問リンク


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

問題を解く


文字列と爆発文字列に入力が付与されている場合は、文字列内で爆発文字列を検索して削除し、再構築された文字列に爆発文字列がある場合は、爆発文字列がないまで削除を繰り返すことで問題を解決します.
  • 文字列を順番に参照し、スタックに格納する
  • スタックのtopと爆発文字列の最後の文字が同じかどうかの比較
  • が同じ場合は、スタックのサイズが爆発文字列のサイズ(範囲外を防ぐ)
    • 以上であることを確認します.
  • スタックの古い値と爆発文字列の比較
  • スタックの古い値が爆発文字列の値と同じである場合、
    • は爆発文字列の長さでスタックから削除されます.
    しかし,スタックは重複者が存在しないため,以前の値と比較することは困難であると考え,ベクトルをスタックとして表して問題を解決する.
    TMI)初めて問題を解くときにfind関数を使うのは簡単な問題だと思いますが、find関数を使うとタイムアウトします.対応するコードも一緒に添付します.

    正しいコード

    #include<iostream>
#include<string>
#include<algorithm>
#include<vector>


using namespace std;

int main() {
	string str1; //입력 문자열
	string boomb; //폭발 문자열
	cin >> str1 >> boomb;

	vector<char> answer;

	

	//#2
	for (int i = 0; i < str1.size(); i++) {
		int count = 0;
		answer.push_back(str1[i]);
		if (answer.back() == boomb[boomb.size() - 1]) { //벡터의 마지막 값과 폭탄 문자열의 마지막 값을 비교
			if (answer.size()>=boomb.size()) { //예외처리
				int count = 0; // 벡터의 이전 값들과 폭탄 문자열의 값들을 비교하며 같은 값을 카운트
				for (int j = 0; j < boomb.size(); j++) { //벡터의 크기만큼 비교
					if(answer[answer.size() - boomb.size() + j] == boomb[j]) count++; 
				}
				if (count==boomb.size()) { 
					answer.erase(answer.end() - boomb.size(),answer.end());
				}
			}
		}
	}
	if (answer.size() == 0) {
		cout << "FRULA";
	}
	else {
		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i];
		}
	}

	/* #1 시간초과
	while(str1.find(boomb)!=string::npos) {
		int n = str1.find(boomb);
		string from = str1.substr(0, n);
		string to = str1.substr(n + boomb.size());
		str1 = from + to;
	}
	if (str1.size() == 0) {
		cout << "FRULA";
	}
	else {
		cout << str1;
	}
	*/



	return 0;
}
    CSSのサイトレイアウト
    ステップ書きアルゴリズム(再帰的でないソート)