글 읽기 - c언어로 작성했는데시간초과라고 나옵니다. for문만 몇개있고 O(N)인데 이러네요

qorwns2716 2년 전 1

본문에 나온 예들을 넣었을때 모두 vsc로 돌렸을때 괜찮은데 무엇이 문제일까요? 시간초과라고 뜹니다.

뭐가 문제인걸까요? for문만 몇개있고 O(N)인 것 같은데, strlen함수가 문제인줄 알고 직접 짜서 했는데도, 잘 안나오네요

#pragma warning (disable: 4996)
#include <stdio.h>
#include <string.h>

int Strlen(char* array) {
	int count = 0;
	while (*array != NULL) {
		array++;
		count++;
	}
	return count;
}

int main(void) {
	
	char word[1000001];
	char alpa[27] = { 0, };
	int max = 0;
	int max_count = 0;
	int target = 0;
	// 65가 A, 90이 Z
	// 97이 a, 122이 z
	scanf("%s", word);

	for (int i = 0; i < Strlen(word); i++) {
		if (word[i] < 97) word[i] = word[i] + 32;
	} // 소문자로 바꾸어 주기
	//printf("%s\n", word); // ok
	//printf("%d\n\n\n",Strlen(word));

	for (int i = 0; i < Strlen(word); i++) {// alpa에 반복되는 횟수만큼 index에 숫자 플러스 해주기.
		alpa[(word[i] - 97)]++;
	} 
	//printf("%d\n\n\n", Strlen(word));

	//printf("\n"); // ok


	// 초기화
	max = alpa[0];
	target = 0;

	for (int i = 0; i < 26; i++) {// 최대 많이 나온 것의 횟수 구하기. ex) aaaab라면 max는 3

		if (max < alpa[i]) {
			max = alpa[i];
			target = i;
		}
	} 
	//printf("%d\n", max); //ok

	for (int i = 0; i < 26; i++) {
		if (max == alpa[i]) max_count++;
		
	} // max가 중복인가? 즉 aaabbbc 에서 a,b 처럼 동시에 나온 숫자가 큰게 2가지 있나?
	//printf("%d\n\n", max_count);

	if (max_count > 1) printf("%c", '?');
	else printf("%c", target + 'A');



	return 0;
}

qorwns2716 2년 전 1

해결했습니다!

strlen함수는 원래 \n을 처음부터 끝까지 찾아서 O(N)이라 for문과 함께쓰면 O(n^2)이 됩니다.

따라서 미리 int len = strlen(array); 같은 식으로 찾아주고,

char word[27] -> int word[27]로 바꾸어줘서 overflow가 나지 않도록 해줍니다

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

문제

문제

출처

ICPC

c언어로 작성했는데시간초과라고 나옵니다. for문만 몇개있고 O(N)인데 이러네요

qorwns2716 2년 전 1

qorwns2716 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말