글 읽기 - 시간초과 해결법이 뭐가 있을까요...?

dlaqudanr 7년 전 0

시간초과가 나네요 ㅠㅠ...

결과는 제대로 나옵니다. ㅜㅠ

strlen도 for문에 쓰지 않았는데 나는거 보니 알고리즘 문제 인거 같은데...

제 알고리즘이 느린가요...?

다른 알고리즘이 뭐가 있는지.. 알려주시면 감사하겠습니다.

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	char word[1000001];
	int max = 0;
	int count = 1;
	char maxch;
	cin >> word;
	
	unsigned long len = strlen(word);
    //len을 strlen으로 초기화 하여 시간을 줄인다.
    
	//대소문자 대문자로 통합시킴
	for (int i = 0; i < len; i++)
	{
		if (word[i] >= 97)
		{
			word[i]=word[i] - 32;
		}

	}
	// 통합 끝
    
    
    // 문자 한개씩 비교해주는 코드 입니다. word[0]은 word[1]부터 입력된 끝까지 비교
    // word[1]은 word[2]부터 비교...
	for (int i = 0; i <len; i++)
	{

		for (int j = i + 1; j < len; j++)
		{
			if (word[i] == word[j])
			{
				count++;
			}

		}
		if (count > max)
		{
			maxch = word[i];
			max = count;
			count = 1;
			if (max>strlen(word) / 2) //2분의1을 넘어가면 어차피 뒤에는 클 수가 없음 반복 종료
				break; 
		}
		else if (count == max)
		{
			maxch = '?';
			count = 1;
		}
		else
			count = 1;
	}

	cout << maxch << endl;
	return 0;
	
	}

codeonwort 7년 전 0

occurence[i] = i번째 알파벳이 출현한 횟수

를 계산하고 occurence[i]가 가장 큰 알파벳을 찾아보세요.

dlaqudanr 7년 전 0

codeonwort 님 감사합니다. 댓글보고 잘 이해했습니다.

제가 올린 코드는 문자가 커질 수록 for문을 수행하는 시간이 엄청나게 걸리는군요!!

제시해주신 방법으로 해결 하였습니다.

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

문제

문제

출처

ICPC

시간초과 해결법이 뭐가 있을까요...?

dlaqudanr 7년 전 0

codeonwort 7년 전 0

dlaqudanr 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말