이 문제에서는 소문자의 입력 문자열이 제공됩니다. 우리의 임무는 m 입력 문자열에서 최대 발생 문자 .
발생 빈도가 같은 값이 여러 개인 경우 사전순으로 더 작은 값을 인쇄해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
string = “programming”
출력
g
솔루션 접근 방식
문제에 대한 해결책을 찾으려면 읽은 문자열을 정렬한 다음 문자열에서 가장 많이 발생하는 문자를 찾을 수 있도록 문자열을 탐색해야 합니다. 우리는 이 문제를 해결하기 위해 해싱 방식(해시 테이블 방식)을 사용할 것입니다. 각 개별 문자를 탐색하고 문자 배열로 해싱하는 것을 해싱이라고 합니다.
일반적으로 해시 배열 크기는 256으로 할당됩니다. 그러나 문자열에 0에서 127 사이의 문자만 포함되어 있으면 크기 128의 해시 테이블을 사용할 수 있으므로 문자열에 따라 해시 테이블 크기를 할당 해제할 수 있습니다.
알고리즘
-
입력 문자열을 읽습니다.
-
문자열에서 최대 발생 문자를 계산하는 함수를 만듭니다.
-
개별 문자의 수를 유지하고 배열을 0으로 초기화하는 배열을 만듭니다.
-
입력 문자열에서 문자 수 배열을 구성합니다.
-
최대 개수 및 결과를 초기화합니다.
-
문자열을 통과하고 서로의 수를 유지합니다.
-
마지막으로 최대 개수의 문자를 찾아 출력합니다.
예시
솔루션 작동을 설명하는 프로그램
#include <bits/stdc++.h>
using namespace std;
char findMaxOccuringChar(char str[]){
int freq[26] = { 0 };
int maxFreq = -1;
char maxFreqChar;
int len = strlen(str);
for (int i = 0; i < len; i++)
freq[str[i] - 'a']++;
for (int i = 0; i < 26; i++)
if (maxFreq < freq[i]) {
maxFreq = freq[i];
maxFreqChar = (char)(i + 'a');
}
return maxFreqChar;
}
int main(){
char str[] = "programming";
cout<<"Maximum occurring character of input string is "<<findMaxOccuringChar(str);
return 0;
} 출력
Maximum occurring character of input string is g