글 읽기 - 이 코드에서 왜 시간초과가 나는 걸까요?

adnyss 7년 전 0

제 코드는 string 을 입력받으면,

입력받은 문자열에서 빈칸(스페이스 바)의 개수를 찾고,

입력받은 형태의 케이스를 분류해서 단어의 개수를 나타내는 코드인데요.

일단 비쥬얼 스튜디오에서는 문제없이 잘 돌아가는데

왜 시간초과가 뜰까요?

혹시 for문 안의 find() 때문에 그런걸까요?

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

int main(){
	string str;
	int cnt=0;
	int startidx,idx;
	startidx=-1;idx=0;
	getline(cin,str,'\n');
	int end=str.size();
	for(int i=0;i<end;i++){
		idx=str.find(' ',startidx+1);
		if(idx!=-1){
		startidx=idx;
		cnt++;}
	}
	if(str[end-1]==' ' && str[0]!=' ')        cout << cnt << '\n';
	else if(str[end-1]==' ' && str[0] == ' ') cout<<cnt-1<<'\n';
	else if(str[end-1]!=' '&& str[0] == ' ')  cout<<cnt<<'\n';
	else cout<<cnt+1<<'\n';
}

qja0950 7년 전 0

for문 안에 처음 idx가 -1인 경우는 end번 str.find()를 실행시키게 되고,

이경우에 O(n^2)의 시간복잡도가 될 듯 합니다.

adnyss 7년 전 1

qja0950 아 역시 그렇군요. 빈칸 없이 알파벳으로만 이루어진 단어일 경우 find()가 end번 실행되네요.

다행히 문제를 해결 했는데,

빈칸이 있는 배열의 인덱스를 찾고 그 인덱스의 양 옆의 문자가 isalpha()....를 이용해서 해결했습니다.

답변 감사합니다^^

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

문제

문제

출처

ICPC

이 코드에서 왜 시간초과가 나는 걸까요?

adnyss 7년 전 0

qja0950 7년 전 0

adnyss 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말