[백준][c] 1157: 단어 공부

https://www.acmicpc.net/problem/1157

1157번: 단어 공부

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

입력

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
	char str[1000000];
	int alpha[26] = { 0 };
	int max = 0;
	int index_max;
	int duplic_max = -1;	//max의 중복 여부  0: 중복 없음   1이상: 중복

	scanf("%s", str);	// A: 65   a: 97

	for (int i = 0; str[i] != 0; i++) {
		for (char j = 'A'; j <= 'Z'; j++) {
			if (str[i] == j || str[i] == j + 32) {
				alpha[j - 'A']++;
			}
		}
	}

	for (int i = 0; i < 26; i++) {
		if (max < alpha[i]) {
			max = alpha[i];
			index_max = i;
		}
	}

	for (int i = 0; i < 26; i++) {
		if (max == alpha[i]) {
			duplic_max++;		//-1로 초기화했기 때문에 max가 하나만 있을 시에 duplic_max = 0
		}
	}

	if (duplic_max == 0) {
		printf("%c\n", 'A' + index_max);
	}
	else {
		printf("?\n");
	}
}

1. 단어를 char형 배열 str에 입력받습니다.
2. 단어의 처음부터 끝까지 탐색하면서 대문자와 소문자를 int형 배열 alpha에 카운팅해줍니다. ( 'A'는 65이고 'a'는 97이기 때문에 32의 차이가 있습니다.)
3. alpha에서 최댓값을 찾아 max에 저장하고, 그 때의 index를 index_max에 저장합니다.
4. max의 중복 여부를 확인하기 위해 alpha를 탐색하면서 max와 같은 값이 있을 때마다 duplic_max++ 해줍니다.
5. duplic_max == 0 일때 중복이 없으므로 해당 대문자를 출력하고, duplic_max != 0 일때는 ?를 출력합니다.

조건문과, 적절한 변수의 선언과 초기화, 문자의 인덱싱과 같은 이해가 많이 필요했던 문제였습니다.

 

---

추가로, 문제에서 단어의 최대 길이를 1,000,000로 지정해줬기 때문에 str[1000000]과 같이 변수를 선언하면 

visual studio 에서는 warning을 표시합니다.

Warning C6262 Function uses '1000132' bytes of stack:  exceeds /analyze:stacksize '16384'.  Consider moving some data to heap. 

stack에서 불필요한 메모리가 심하게 낭비되고 있기 때문입니다.

따라서 실제 구현할 시에는 malloc으로 필요한 만큼만 stack의 메모리를 할당받아서 메모리 낭비를 최소한으로 해야할 것입니다.