글 읽기 - 시간 초과 어떻게 해결해야 할까요?

mystika 7년 전 0

문자열 끝에서부터 처음으로 재귀적으로 문자가 폭탄 문자열과 매치하는지 확인하고 맞으면 _로 바뀌게 한 뒤 매번 체크할때마다 _를 만나면 폭탄 문자열의 길이만큼 건너뛴 후 체크하게 하였는데 48% 이전 케이스는 제대로 동작하는것 같은데 48%에서 계속 TLE가 나옵니다.

어떻게 접근해야 더 빠르게 동작하게 만들 수 있을까요?

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
string line,bomb;
int linesize, bombsize,totalcount=0;
int repl(int pos,int bombpos=0){
	if(pos>=linesize) return 0;
	if(line[pos] == '_') return repl(pos+bombsize,bombpos);
	if(line[pos] == bomb[bombpos]){
		if(bombpos+1 == bombsize){
			line[pos]='_';
			totalcount++;
			return 1;
		}else {
			if(repl(pos+1,bombpos+1)){
				line[pos]='_';
				totalcount++;
				return 1;
			}

		}

	}
	return 0;
}
int main(){
	int i;
	string res="";
	cin>>line>>bomb;
	linesize = line.size();
	bombsize = bomb.size();
	for(i=linesize-1;i>=0;i--){
		repl(i);
	}
	if(totalcount==linesize){
		cout<<"FRULA";
		return 0;
	}
	for(i=0;i<linesize;i++)
		if(line[i]!='_') printf("%c",line[i]);
		else i+=bombsize-1;
}

pl0892029 7년 전 0

스택으로 짜시면 쉬울꺼같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과 어떻게 해결해야 할까요?

mystika 7년 전 0

pl0892029 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말