[백준/C++] 1371번 가장 많은 글자

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

1371번: 가장 많은 글자

 

문제 분석

영어권에서는 어떤 글자가 다른 글자보다 많이 쓰인다. 예를 들어, 긴 글에서 약 12.31%를 차지하는 글자는 e이다. 어떤 글이 주어졌을 때, 가장 많이 나온 글자를 출력하라.

입력으로는 첫째 줄부터 글의 문장이 주어진다. 글은 최대 50개의 줄로 이루어져 있고, 각 줄은 최대 50개의 글자로 이루어져 있다. 각 줄에는 공백과 알파벳 소문자만 있다. 문장에 알파벳은 적어도 하나 이상 있다.

출력으로는 첫째 줄에 가장 많이 나온 문자를 출력한다. 여러 개일 경우에는 알파벳 순으로 앞서는 것부터 모두 공백없이 출력한다.

공백이 포함되어 있는 문장이므로 getline 함수를 사용해주고, 문제를 해결하는 키 포인트는 알파벳의 등장 횟수를 세는 배열을 하나 만드는 것이다.

아래 코드를 보자

#include <iostream>
#include<string>
using namespace std;

int alpha[26];

int main()
{
	string str[50];
	int max=-1;


	for (int i = 0; i < 50; i++) {
		getline(cin, str[i]);
		
		for (int j = 0; j < str[i].size(); j++) {
			alpha[str[i][j]-97]++;
		}
	}
	for (int i = 0; i < 26; i++) {
		if (max <= alpha[i]) {
			max = alpha[i];
		}
	}
	for (int i = 0; i < 26; i++) {
		if (alpha[i] ==max) {
			cout << (char)(i + 97);
		}
	}
}

문제 풀이

1. 알파벳의 등장 횟수를 세어줄 배열 alpha[26] 선언

2. str[50] 선언 후, 한줄 씩 차례대로 저장

3. 그리고 그 한 줄을 for문을 통해 전체 탐색 -> str[i][j]-97을 하게 되면, 알파벳 소문자들이 abcdedf......에서 0,1,2,3,4...로 바뀌게 되고 이것들을 배열의 인덱스로 사용하는 원리이다.

4. 예를 들어 ababc일 때 a는 -97을 하게 되면 0이 되고, 마찬가지로 b는 1, c는 2가 된다.

따라서 배열 alpha[0]++, alpha[1]++ ...가 이루어지면서 알파벳들의 등장 횟수를 저장할 수 있게 된다.

5. -1로 설정된 max값과 비교를 통해 배열의 값중 가장 큰 값(=가장 많이 등장한 횟수)이 max값이 된다.

​6. 그렇게 설정된 max값과 alpha배열의 비교를 통해 가장 많이 등장한 알파벳 하나가 아닌, 여러 개를 출력할 수 있게 한다. 또한 알파벳의 순서를 이용했으므로 문제에서 요구한 정렬 역시 자연스레 해결할 수 있다.

※ 계수 정렬과 매우 유사한 느낌!