글 읽기 - 단어공부 c언어) 시간초과 뜹니다.

leewwo2o 6년 전 0

시간초과가 뜨네요 이 방법 말고 다른 방법이 있나요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int main() {
	char s[1000002] = { 0 };
	int a[27] = {0};
	int cnt = 0, i,max=-1,in=0;
	gets(s);
	//scanf("%s", s);
	for (int i = 0; i <= strlen(s); i++) {
		a[s[i] - 'a']++;
	}
	for (int i = 0; i <27; i++) {
		if (a[i] > max) {
			max = a[i];
			in = i;
			cnt = 0;
		}
		else if (a[i] == max) 
			cnt++;
	}
	if (cnt == 0)
		printf("%c", in + 'a');
	else
		printf("?");
	return 0;
}

sgchoi5 6년 전 1

strlen 이 매번 비교할 때에 동작이 되어야 합니다.

for 문 밖으로 빼서 한 번막 수행되도록 하셔야 할 듯 하네요.

kyhdudgns113 6년 전 1

10번째 줄에서, for 문을 한번 돌때마다 strlen 함수를 호출하네요. 만약 단어의 길이가 100만이라면, strlen 함수를 백만번 호출하게 되겠죠!

그런데 이 strlen 함수는 문자열에서 null 문자가 들어올때까지 char 배열을 하나하나씩 읽습니다.

그러면 문자열의 길이가 100만이라면, strlen 함수 하나당 100만번, 10번째 줄에서 strlen 함수를 100만번 호출하게 되므로 총 1조번의 연산을 하게 되겠네요!

int len = strlen(s);

for (int i = 0; i < len; i++) {
a[s[i] - 'a']++;
}

으로 고쳐주시면 됩니다.

그리고 소스코드를 보니 이것 말고도 수정할 부분이 몇개 있네요!

1. 문자열의 끝에는 null문자가 들어갑니다. 이것을 읽을 필요가 없겠죠? 따라서, 위에 적어놓았듯이 i <= len 을 i < len 으로 고쳤습니다.

2. 입력에는 대문자도 들어갈 수 있습니다.

3. 출력은 대문자로 나와야합니다.

leewwo2o 6년 전 0

아 감사합니다 이제 알꺼 같습니다

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

문제

문제

출처

ICPC

단어공부 c언어) 시간초과 뜹니다.

leewwo2o 6년 전 0

sgchoi5 6년 전 1

kyhdudgns113 6년 전 1

leewwo2o 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말