글 읽기 - [9935] C++ 메소드 이용하여 풀이하면 원래 시간초과가 걸리나요?

mycool0905 4년 전 0

제가 C++ 라이브러리 이용해서 문제를 쉽게 풀려고 했습니다.

제가 생각하기에는 O(N)으로 탐색이 끝나는 코드를 작성했다고 생각했는데, 그게 아니더군요.

혹시 제가 잘못 생각한건가요?

#include <iostream>
#include <string>

using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	string input, bomb;

	cin >> input;
	cin >> bomb;

	int findPosition = input.find(bomb);
	while (findPosition != -1) {
		input = input.substr(0, findPosition).append(input.substr(findPosition + bomb.size(), input.size()));
		if (findPosition - (int)bomb.size() >= 0)
			findPosition = input.find(bomb, findPosition - bomb.size());
		else
			findPosition = input.find(bomb);
	}

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

	return 0;
}

kcm1700 4년 전 0

input.substr(0, findPosition).append(input.substr(findPosition + bomb.size(), input.size()));

이 라인이 이미 선형시간이네요.

mycool0905 4년 전 0

@kcm1700
아 저 메소드를 시간에 고려 안했네요.

다시 생각해보도록 하겠습니다!

감사합니다!

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

문제

문제

출처

ICPC

[9935] C++ 메소드 이용하여 풀이하면 원래 시간초과가 걸리나요?

mycool0905 4년 전 0

kcm1700 4년 전 0

mycool0905 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말