글 읽기 - 시간초과>>틀렸습니다>>시간초과의 반복입니다.

behappyis 7년 전 0

시간초과>>틀렸습니다>>시간초과의 반복입니다.

조언을 부탁드립니다.

첨에 풀기시작한데로 string으로 계속 도전하고 있는데..

어느 부분이 시간을 잡아먹는 부분일까요?

31라인 sTmp=sTmp.substr(0,point); 의 substr처리일까요?

#include <iostream>
using namespace std;
int main(void)
{
	string sInput,sBomb,sTmp;
	cin >> sInput >> sBomb;
	int sBombSize=sBomb.length();
	int point=0;
	int k;
	bool bMatch;
	for(int i=0;i<sInput.length();i++)
	{
		sTmp+=sInput[i];
		point++;
		if(point>=sBombSize && sInput[i]==sBomb[sBombSize-1])
		{
			bMatch=true;
			k=0;
			for(int j=sBombSize-1;j>=0;j--)
			{
				if(sTmp[point-1-k]!=sBomb[j])
				{
					bMatch=false;
					break;
				}
				k++;
			}
			if(bMatch)
			{
				point-=sBombSize;
				sTmp=sTmp.substr(0,point);
			}

		}	
	}
	if(point==0)
	{
		cout << "FRULA";
	}
	else
	{
		cout << sTmp;
	}
	cout << endl;
	return 0;
}

mathjuny 7년 전 0

cin 말고 scanf 쓰세요

portableangel 7년 전 0

31번 줄이 O(N)이어서 시간이 터집니다.

for(int i=0;i<sBobmSize;i++) sTmp.pop_back();

으로 작성하시고, C++11 혹은 C++14로 제출해보세요

behappyis 7년 전 0

mathjuny

답변감사드립니다.

scanf로 string변수에 직접 담으려하니 실행하다가 다운되네요. 제가 아직 미숙해서...

portableangel

답변감사드립니다.

작성해주신 for(int i=0;i<sBobmSize;i++) sTmp.pop_back(); 로 C++11로 하니 해결되었습니다.

pop_back() 관련도 찾아보며 많은 공부가 되었습니다.

감사합니다.

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

문제

문제

출처

ICPC

시간초과>>틀렸습니다>>시간초과의 반복입니다.

behappyis 7년 전 0

mathjuny 7년 전 0

portableangel 7년 전 0

behappyis 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말