글 읽기 - 시간초과 질문이요(C)

sdtgzx 3년 전 0

\n까지 입력을 받고 ' ' 만 찾아서 카운트하는데 시간초과가 납니다.

어디가 문제일까요??

/*
단어의 개수
*/

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
int ans;
char ch[1000001];
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%[^\n]s", ch);
	if (strlen(ch) == 0) {
		printf("0");
		return 0;
	}
	for (int i = 0; i <= strlen(ch)-1; i++) {
		if (ch[i] == ' ')
			ans++;
	}
	printf("%d", ans);
	return 0;
}

dldyddlwl 3년 전 0

아래의 for문으로 하니까 시간초과가 해결되더군요. 아마 strlen이 size_t라는 unsigned 타입형을 리턴하는데, 거기에 -1이 되면서, 언더플로우가 일어나서

루프가 지나치게 길게 돌게 된 것 같습니다.

그런데 위에서 strlen == 0을 분명 걸러냈는데도 아래에서 걸리는 게 이상하네요. 이 부분은 잘 모르겠네요...

for (int i = 0; i <= strlen(ch)-1; i++)    // 언더플로우가 일어날 가능성, unsigned가 0일 때
                                            // 1을 빼면, -1이 아닌, 최댓값이 나옴
    
for(int i =0; i< strlen(ch); i++)        // 아래와 같이 하니 시간초과해결

djm03178 3년 전 0

i < strlen(ch)도 원래는 시간 초과가 나는 것이 일반적이지만, 컴파일러의 마법의 최적화에 의해 통과될 뿐입니다.

for문의 조건문은 for문이 한 바퀴 돌 때마다 실행되며, strlen이 그때마다 하는 작업은 문자열의 시작점부터 출발해서 한 문자씩 확인해서 널 문자가 나타나는 지점을 찾는 것입니다. 그래서 문자열의 길이에 비례하는 시간이 걸리고, 이 작업을 문자열의 길이만큼 반복하므로 총 시간 복잡도는 문자열의 길이의 제곱에 비례합니다.

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

문제

문제

출처

ICPC

시간초과 질문이요(C)

sdtgzx 3년 전 0

dldyddlwl 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말