글 읽기 - C / 틀린 답이라 뜨는데, 반례가 궁금합니다.

dltpt99 4년 전 0

전체 매커니즘은

문자열 입력받은 뒤, 문자열 전체를 배열로 돌려서 string[i] 의 알파벳이 대문자라면 첫번째 if문을 패스합니다. 소문자라면 대문자로 바꿔주고 ( string[i] -=32 ) 이 알파벳이 사용된 횟수를 max변수와 비교하여 최대값을 찾습니다. ( if문에서 ++arr[string[i]-65] > max ) max_ch는 가장많이 나온 알파벳을 저장.

그 다음 for문은 최대값이 중복되는지 비교합니다. max_ch-65 != i 는 가장많이 나온 알파벳의 인덱스를 비교에서 제외 / max==arr[i] 는 가장많이 나온 횟수와 같은 값이 다른 알파벳에도 있는지 비교하는 항목. 이 부분에서 만약 해당하는 값이 나온다면 ? 를 출력하고 종료. 해당하는게 없다면 max_ch를 출력.

제가 잘못 구성한 부분이나, 반례가 궁금합니다.

#include <stdio.h> 
#include <string.h>
main() {
	char string[1000001];
	scanf("%s", string);

	char arr[26] = { 0, };
	int max = 0; // 가장 많이 나온 횟수.
	char max_ch; // 가장 많이 나온 알파벳 저장.
	//대문자 65~90
	//소문자 97~122

	int strlength = strlen(string);
	
	for (int i = 0; i < strlength; i++) {
		if (string[i] > 91) 
			//소문자라면 a~z. 97~122.
			//대문자로 변환. -32
			string[i] -= 32;
		
		if (++arr[string[i] - 65] > max) {
			max = arr[string[i] - 65];
			max_ch = string[i];
		}
			
	}

	for (int i = 0; i < 26; i++) {
		// 가장많이 나온 알파벳의 인덱스는 제외.
		// 가장많이 나온 알파벳과 같은 횟수만큼의 다른 알파벳
		if (max_ch-65 != i && max==arr[i]) {
			printf("?");
			exit(0);
		}
	}
	printf("%c", max_ch);
	
}

dyk777 4년 전 1

arr 배열은 각 알파벳의 등장 횟수를 담는 배열로 보이는데,

char로 선언한 이유가 있나요?

slah007 4년 전 1

윗 분이 지적하신대로, 단어 길이가 최대 1,000,000 이므로 arr의 최댓값이 1,000,000인데, 최댓값이 255인 char형 배열로 선언하면 오버플로우가 납니다. arr을 int형 으로 수정하면 해결될 것 같습니다.

djm03178 4년 전 0

https://www.acmicpc.net/board/... 에 굵은 글씨로 언급된 사항입니다.

dltpt99 4년 전 0

세 분 모두 감사합니다. 단어 관련 문제를 풀다보니 저도모르게 출현 빈도를 카운트하는 배열까지 char로 선언했네요 ^^:;;; int로 바꾸니 바로 정답이네요.

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

문제

문제

출처

ICPC

C / 틀린 답이라 뜨는데, 반례가 궁금합니다.

dltpt99 4년 전 0

dyk777 4년 전 1

slah007 4년 전 1

djm03178 4년 전 0

dltpt99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말