글 읽기 - c++ strlen 시간초과 질문드립니다.

spacein1001 4년 전 1

strlen을 사용해서 시간초과가 발생하는 것 같습니다.

어떻게 바꾸어야 할지 감이 안오는데 설명해주시면 감사하겠습니다.

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int cnt[26]={0,},max=-100,maxi,N;
	char c[1000000];
	
	cin >> c;
	
	for(int i=0;i<strlen(c);i++)
	{
		if(c[i]>='A'&&c[i]<='Z')
		{
			cnt[c[i]-'A']++;
		}
		
		if(c[i]>='a'&&c[i]<='z')
		{
			cnt[c[i]-'a']++;
		}
	}
	
	for(int i=0;i<26;i++)
	{
		if(cnt[i]>max)
		{
			max=cnt[i];
			maxi=i;
		}
	}
	
	for(int i=0;i<26;i++)
	{
		if(cnt[i]==max)
		{	
			N++;
			
			if(N>1)
			{
				cout << "?";
				return 0;
			}
		}
	}
	
	cout << char (maxi+'A');

}

bupjae 4년 전 1

strlen 의 시간복잡도는 O(n) 입니다

따라서 18번째줄의 반복문의 시간복잡도는 O(n^2) 이 됩니다.

strlen 을 반복문 바깥에서 사용하세요.

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

문제

문제

출처

ICPC

c++ strlen 시간초과 질문드립니다.

spacein1001 4년 전 1

bupjae 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말