글 읽기 - 시간초과 문제입니다.

dydrnjs518 5년 전 0

스택을 안쓰고 구현했습니다.

시간 초과가 나는 이유를 모르겠습니다.

조언부탁드립니다.

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);

	string str;
	cin >> str;

	string bomb;
	cin >> bomb;

	int i = 0;
	
	while (str[i] != '\0') {							// 문자열에서 널값이 나올때까지 순회한다.
		if (str[i] == bomb[0]) {						
			int cnt = 1;
			for (int j = 1; j < bomb.size(); j++) {		// 폭발 문자열과 같은 문자열이 있는지 확인한다. 
				if (!(str[i + j] == bomb[j]))			
					break;
				cnt++;
			}
			if (cnt == bomb.size()) {					// 폭발 문자열과 같은 문자열이 있으면
				str.erase(i, cnt);						// Algorithm함수인 erase로 삭제후
				i -= bomb.size();						// 폭발문자열길이만큼 i를 앞으로 땡긴다.
				if (i < 0)
					i = -1;
			}
		}
		i++;
	}

	str.empty() ? cout << "FRULA" << endl : cout << str << endl;
}

djm03178 5년 전 0

erase 함수는 해당 구간을 지운 후 뒤의 나머지 문자열을 전부 앞으로 끌어와야 합니다. 그래서 그 때마다 O(str.size()) 시간이 걸립니다.

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

문제

문제

출처

ICPC

시간초과 문제입니다.

dydrnjs518 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말