글 읽기 - 자꾸 시간초과가 뜨는데 뭐가 문제인지좀 봐주세요..

minhas2 7년 전 0

피자먹고싶었는데

피자는커녕 이 한문제에 쩔쩔매고있었어요..

ㅠㅠㅠ...

시간초과 원인이 될만한 코드가 뭐가있을까요...?

#include <iostream>

using namespace std;

const int maxsize = 100000;
int main()
{
	char* input = new char[maxsize];
	cin >> input;
	int count = 0;
	for (count = 0; input[count] != NULL; count++) {}

	int l = count;
	int output=1;

    //s=왼쪽문자 기준으로, l=오른쪽부터 문자열비교하면서
    //일치하게되면 가장긴 문자 카운팅
    //문자열 끝까지 반복 위의과정
	for (int s = 0; s < count; s++) {
		for (l = count-1; l >= s; l--) {
			if (input[s] == input[l])
			{
				int forcomC = 1;
				int ss = s, ll = l; //ss=왼쪽인덱스 ll=오른족인덱스
				while (++ss < count&& --ll >= 0 && input[ss] == input[ll]) {
					forcomC++;
					if (ss == ll) {//일치하는 문자의 갯수가 홀수개일경우
						forcomC = forcomC * 2 - 1;
						break;
					}
					else if (ss-1 == ll) {//문자의 갯수가 짝수개인경우
						forcomC = forcomC*2-2 ; break;
					}
				}

				if (forcomC > output) output = forcomC;//가장 긴 문자열길이 비교
			}
		}

	}

	cout << output;

    return 0;
}

dongwon0427 6년 전 1

네 이렇게 짜면 O(n^2)정도의 시간복잡도가 나옵니다. 다른 알고리즘을 쓰셔야 될거에요

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

문제

문제

출처

ICPC

자꾸 시간초과가 뜨는데 뭐가 문제인지좀 봐주세요..

minhas2 7년 전 0

dongwon0427 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말