백준 1157 : 단어공부 c언어

문제

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

입력

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

출력

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

 

처음에는 단순히 문자열을 모두 비교하면서 가장많이 나오는 수를 찾아내서 출력하고, max를 통해 똑같이 많이사용된 알파벳을 찾아내서 ?를 출력해줄 생각이었는데, oj에 넣어놓고보니 시간초과가 나왔다.

시간초과가 나오는 이유에 대해 고민해보았는데 3번째 for문이 각 문자열이 몇번나오는지에대해 비교하는 for문인데 큰for문이 비교할 문자, 안에 있는 for문이 비교할 문자를 제외한 나머지 문자를 모두 확인해주는 for문인데 만약 문자열의 길이가 1,000,000이라고 하였을때 1,000,000*999,999==999,999,000,000정도의 반복이 필요하다 생각하니 너무 긴 시간이 나올것이라고 생각이 들어 다른 방식으로 풀어야겠다는 생각을 하였다.

 

첫번째 코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
	char alp[1000000];//문자열
	char maxalp;//가장많이나오는문자
	int max;//가장많이나오는문자의 개수
	int cnt = 0;//문자가 몇번 나왔는지
	int chk = 0;//가장많이나오는문자가 여러개임을 체크해주는 변수
	scanf("%s", alp);
	for (int i = 0; i < strlen(alp); i++)/*대,소문자를 구분하지 않
		는다고 했기때문에 모든문자를 대문자로 바꿈*/
	{
		if (alp[i] >= 'a' && alp[i] <= 'z')
		{
			alp[i] -= ('a' - 'A');
		}
	}
	maxalp = alp[0];//첫번째 문자를 기준
	for (int i = 1; i < strlen(alp); i++)//첫번째문자가 몇번나왔고, 이것을 기준
	{
		if (maxalp == alp[i])
		{
			cnt++;
		}
	}
	max = cnt;
	cnt = 0;
	for (int i = 0; i < strlen(alp); i++)//각 문자가 몇번 나오는지
	{

		for (int j = 0; j < i; j++)
			//해당되는문자를 제외한 다른문자와 비교하여 몇번나오는지
		{
			if (alp[i] == alp[j])
			{
				cnt++;
			}
		}
		for (int j = i + 1; j < strlen(alp); j++)
			//해당되는문자를 제외한 다른문자와 비교하여 몇번나오는지
		{
			if (alp[i] == alp[j])
			{
				cnt++;
			}
		}
		if (max < cnt)
			//만약 최대값max보다 큰값이 나오면 max를 재설정
		{
			max = cnt;
			maxalp = alp[i];
			chk = 0;//더 큰수가 나왔으니 만약 같은 횟수만큼나온문자가 여러개여서 체크해놨던chk초기화
		}
		else if (max == cnt && maxalp != alp[i])
			//만약 같은횟수만큼 나온 문자가 여러개라면 체크chk변수 설정 
		{
			chk = 1;
		}
		cnt = 0;
	}
	if (chk == 1)
		//체크가 설정되어있다면 ?
	{
		printf("?");
	}
	else
		//아니라면 maxalp 출력
	{
		printf("%c", maxalp);
	}
}

다른방법으로 0을a, 1을 b 이런식으로 인덱스를 알파벳이라고 임의로 정하고, 각 인덱스에 알파벳이나온 개수를 저장하여 비교하는 방법을 사용하였다. 이런방식으로 하니 확실이 코드의 길이도 줄고 for문의 사용정도, 이중for문도 사용하지 않게되면서 확실히 시간이 줄어들었다.

또한 for문안에서 배열을 계속 불러오면 시간이 많이 드니 임의의 변수에 미리 strlen의 숫자를 저장시켜 사용하는 것도 시간을 줄이는 방식이라는 것을 알았다.

 

수정한 코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
	int alp[26] = { 0 },max=0,chk=0,num,len;
	char sen[1000000];
	scanf("%s", sen);
	len = strlen(sen);

	for (int i = 0; i < len; i++)
	{
		if (sen[i] >= 'A' && sen[i] <= 'Z')
		{
			alp[sen[i] - 'A']++;
		}
		else if(sen[i] >= 'a' && sen[i] <= 'z')
		{
			alp[sen[i] - 'a']++;
		}
	}
	for (int i = 0; i < 26; i++)
	{
		if (max < alp[i])
		{
			max = alp[i];
			chk = 0;
			num = i;
		}
		else if (max == alp[i])
		{
			chk = 1;
		}
	}
	if (chk == 1)
	{
		printf("?");
	}
	else
	{
		printf("%c",num + 'A');
	}
}