이 문제에서는 모두 소문자로 된 문자 배열이 제공됩니다. 우리의 임무는 배열에서 접두어의 최대 발생입니다. .
발생 횟수가 최대인 비어 있지 않은 접두사의 발생 횟수를 계산해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input : string = “xyyzkxyyzk” Output : 2
해결 방법
논리는 배열의 접두사가 항상 분명히 문자열의 첫 번째 문자를 포함해야 하고 반복되는 항목도 포함해야 한다는 것을 시각화하는 것입니다. 그리고 문자열의 첫 번째 문자는 분명히 문자 수가 가장 적은 접두사입니다. 따라서 최대 발생 접두사는 문자열의 첫 번째 문자가 될 것입니다. 따라서 이제 문자열의 첫 번째 문자 수를 찾는 작업이 축소되었습니다.
알고리즘
-
일련의 소문자 알파벳을 읽습니다.
-
필요한 접두사의 개수를 반환하는 함수를 만듭니다.
-
초기화 횟수=0.
-
문자열의 첫 번째 문자의 빈도를 찾습니다.
-
문자열의 접두어가 최대로 나타나는 문자열의 첫 번째 문자의 빈도를 인쇄합니다.
예시
솔루션의 작동을 설명하는 프로그램,
#include <iostream>
using namespace std;
int findPrefixOccurence(string str){
char chars = str[0];
int countOccrence = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == chars)
countOccrence++;
}
return countOccrence;
}
int main(){
string str = "xyyzxxyyzxyxx";
cout<<"The maximum occurence of prefix in the array is "<<findPrefixOccurence(str);
return 0;
} 출력
The maximum occurence of prefix in the array is 6