글 읽기 - C언어 Strlen에 관하여 질문드립니다.

jibaek0513 3년 전 0

코드는 제가 정답으로 인정받은 코드입니다

이전에는 16줄에 len을 초기화하지않고 바로 strlen(str)로 하였는데 그 때는 시간초과가 떠서 실패가 뜨더군요

이후에 변수 len을 따로 저장하여서 미리 문자열의 길이를 받아서 비교하였고 이 때는 성공이라고 떴습니다

둘의 차이점이 무엇인가요? 초보 프로그래머에게 알려주시면 감사하겠습니다(__)

#define ARR_LEN 26

int main() 
	
{
	char str[1000000]; 
	int arr[ARR_LEN]={0};
	int i,j,max=0,count=0,idx=0;
	int len;

	scanf("%s",str); //문자열 입력

	len =strlen(str);

	/* 알파벳별 횟수 저장 */
	for(i=0;i<len;i++)
	{
		for(j=0;j<ARR_LEN;j++)
		{
			if(str[i] == 'a'+j)
				arr[j] += 1;
			if(str[i] == 'A'+j)
				arr[j] += 1;
		}
	}
	
	max = arr[0];

	/* 횟수가 가장 많은 인덱스 추출 */

	for(i=0;i<ARR_LEN;i++)
	{
		if(max < arr[i])
		{
			max=arr[i];
			idx = i;
		}
	}

	/* 최고 인덱스가 복수인지 확인 */

	for(i=0;i<ARR_LEN;i++)
	{
		if(max == arr[i])
			count++;
	}

	if(count>1) //max가 두개이상일시
		printf("?\n");
	else
		printf("%c\n",idx+65);
	
	return 0;
}

ehdrmsl2001 3년 전 1

strlen의 시간 복잡도가 O(n)이라서 반복문과 같이 쓰이면 그 시간 복잡도는 O(n^2)이기 때문에 시간초과가 납니다.

쉽게 말해서 i<strlen(str)을 할 때 마다 함수가 호출되기 때문이라고 보시면 됩니다.

jibaek0513 3년 전 0

@ehdrmsl2001 아하 함수가 반복적으로 호출되는게 문제군요 감사합니다!

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

문제

문제

출처

ICPC

C언어 Strlen에 관하여 질문드립니다.

jibaek0513 3년 전 0

ehdrmsl2001 3년 전 1

jibaek0513 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말