글 읽기 - c언어 반례 질문드립니다.

jiho264 2년 전 0

예제 모든 경우 수 vs studio에서 6으로 잘 나옵니다.

질문 게시판에 있는 모든 반례 다 집어넣어 봤습니다.

제가 부족한 점이 무엇이 있을까요? 처음엔 백 만칸 때문에 타임오버인 줄 알고 while로 받아들이는 것도 간소화 해봤습니다.

단어를 정확히 파악하기 위해 소문자로 변환하고 소문자+공백or엔터orNULL인 경우에 count++ 하게 짰습니다.

_a_ == 1

_a\n == 1

_ == 0

\n == 0

' ' (미입력) == 0

이 코드에서 들어맞지 않는 반례를 못 찾겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int main() {
	char a[1000005] = { 0 };
	int count = 0;
	int i = 0;
	while (a[i-1]!=0) {
        // 실행 횟수를 줄이기 위해 끊기는 점 지정. 배열도 여유있게 1,000,005로 지정
		scanf("%c", &a[i]);
		if ('A' <= a[i] && a[i] <= 'Z') a[i] += 'a' - 'A';
        // 모든 대문자는 소문자로 바꿨음.
		i++;
	}

	for (int i = 0; i < strlen(a); i++) {
        // 현재 글자가 소문자인데 다음 글자가 공백 or 엔터 or NULL일 경우 count++/
		if ('a' <= a[i] && a[i] <= 'z' && (a[i + 1] == ' ' || a[i + 1] == 0 || a[i + 1] == 10)) count++;

	}
	printf("%d", count);
}

minkc01 2년 전 0

8번째 줄에서 while문 맨 처음 조건 확인할 때 i = 0이므로 조건문이 a[-1] != 0 이 됩니다.

제 컴퓨터에서 실행시에는 이것 때문에 실행하자마자 바로 0 출력하고 종료됩니다.

minkc01 2년 전 0

strlen자체가 시간복잡도가 O(n)입니다.

n번 도는 for문 내에서 strlen을 호출하니 전체 시간복잡도는 O(n^2)이 됩니다.

strlen을 한 번만 호출하게 수정해보세요.

jiho264 2년 전 0

시간복잡도에 관한 조언 감사합니다.

그런데 결국 관건은 반례였네요.

단어가

{ ~~~, 'a', \n, NULL, ~~~} 식으로

~~a(엔터)인 경우를 지워야했어요.. 아이구 두야.. 감사합니다.

덕분에 짧고 빠른 코드로 성공했습니다.!!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int main() {
	//freopen("input.txt", "r", stdin);
	char a[1000010] = { 1 };
	int count = 0;
	for (int i = 1; i < 1000010; i++) {
		scanf("%c", &a[i]);
		if ('A' <= a[i-1] && a[i-1] <= 'z' && a[i] == ' ') count++;
		else if ('A' <= a[i-1] && a[i-1] <= 'z' && a[i] == 0) count++;
		else if ('A' <= a[i-1] && a[i-1] <= 'z' && a[i] == 10) count++;
		else if (a[i] == 0) break;
	}
	printf("%d", count);
}

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

문제

문제

출처

ICPC

c언어 반례 질문드립니다.

jiho264 2년 전 0

minkc01 2년 전 0

minkc01 2년 전 0

jiho264 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말