[C언어] Backjoon_Code 1157, 단어 공부

| 문제

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

 

| 입력

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

 

| 출력

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

 

| 예제 입력 1

Mississipi

 

| 예제 출력 1

?

 

| 예제 입력 2

zZa

 

| 예제 출력 2

Z

 

| 문제의 키 포인트

1. 문제의 목적: 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 것

2. 이 때 주어지는 단어에서 대문자와 소문자를 구분하지 않는다는 점.

3. 주어지는 단어의 길이는 1,000,000을 넘지 않는다는 점.

4. 출력의 조건은 두 가지

첫 번째, 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다.

두 번째, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

 

| 해결방안(Solution)

1. 가장 많이 사용된 알파벳 = 숫자로 생각한다면? 최대값 or 최소값 찾기와 유사한 패턴이다.

2. ASCII 코드표 활용하기

 

| 소스코드 1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int main(void)
{
	char input[1000000];
	int count[26] = { 0, };
	int i,j, max; // i,j: 반복 변수, max: 최대값
	int select = 0;
	int result = 0;

	// 문자 입력부
	scanf("%s", input);

	// 각 문자 수 계산부
	for (i = 0; i < strlen(input); i++)
	{
		for (j = 65; j < 91; j++)
		{
			if ((int)input[i] == j || (int)input[i] == j+32)
			{
				count[j - 65]++;
			}
		}
	}

	// 최대 문자 수 계산부
	max = count[0];
	for (i = 0; i < 26; i++)
	{
		if (max < count[i])
		{
			max = count[i];
			select = i;
		}
	}

	// 가장 많이 사용된 알파벳이 여러 개 존재하는지 검사
	for (i = 0; i < 26; i++)
	{
		if (max == count[i])
		{
			result++;
		}
	}

	// 결과 출력부
	if (result > 1)
	{
		printf("?\n");
	}
	else
	{
		printf("%c", select + 65);
	}

	return 0;
}

문자 A = 65, ..., Z = 90, a = 97, ..., z = 122 라는 점을 착안하여 조건부를 작성해보았습니다.

작동에는 문제가 없었지만, 정작 백준에서 제출시에는 시간초과라는 오류가 나더군요.

 

| 소스코드 2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int main(void)
{
	char input[1000000];
	int count[26] = { 0, };
	int i,j, max; // i,j: 반복 변수, max: 최대값
	int select = 0;
	int result = 0;

	// 문자 입력부
	scanf("%s", input);

	// 각 문자 수 계산부_소문자
	for (i = 'a'; i <= 'z'; i++)
	{
		for (j = 0; j < strlen(input); j++)
		{
			if (i == input[j])
			{
				count[i - 'a']++;
			}
		}
	}

	// 각 문자 수 계산부_대문자
	for (i = 'A'; i <= 'Z'; i++)
	{
		for(j = 0; j < strlen(input); j++)
		{ 
			if (i == input[j])
			{
				count[i - 'A']++;
			}
		}
	}

	// 최대 문자 수 계산부
	max = count[0];
	for (i = 0; i < 26; i++)
	{
		if (max < count[i])
		{
			max = count[i];
			select = i;
		}
	}

	// 가장 많이 사용된 알파벳이 여러 개 존재하는지 검사
	for (i = 0; i < 26; i++)
	{
		if (max == count[i])
		{
			result++;
		}
	}

	// 결과 출력부
	if (result > 1)
	{
		printf("?\n");
	}
	else
	{
		printf("%c", select + 'A');
	}

	return 0;
}

아무래도 각 문자 계산부에서 시간이 많이 걸리는 것 같아, 해당 부분을 소문자, 대문자로 나누어 각각 반복문을 돌리는 형태로 구성을 바꾸어 보았습니다. 이 경우는 시간초과가 안나더군요. 추가적으로 숫자로 표기했던 문자를 문자 형태로 표시하여 가독성을 높혔습니다.

 

그럼 오늘도 즐거운 코딩!

 

| 문제 출처

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

1157번: 단어 공부