이 문제에서는 모두 소문자로 이루어진 문자 배열이 주어지며, 우리의 목표는 배열에서 가장 많이 등장하는 접두사(prefix)의 최대 출현 횟수를 구하는 것입니다.
즉, 비어 있지 않은(non-empty) 접두사들 중에서 출현 횟수가 최대가 되는 값을 계산해야 합니다.
문제를 이해하기 위해 예제를 살펴보겠습니다.
입력 : string = “xyyzkxyyzk” 출력 : 2
접근 방식(Solution Approach)
핵심 아이디어는 간단합니다. 문자열의 어떤 접두사든 반드시 첫 번째 문자를 포함하게 되므로, 해당 접두사가 반복해서 등장할 때마다 첫 번째 문자 역시 함께 등장합니다. 또한 문자열의 첫 글자 하나만으로 이루어진 부분은 가장 짧은 형태의 접두사입니다.
따라서 가장 많이 등장하는 접두사는 반드시 문자열의 첫 번째 문자일 수밖에 없습니다. 결국 이 문제는 “문자열에서 첫 번째 문자가 몇 번 나타나는지 세는 문제”로 단순화됩니다.
알고리즘
소문자 알파벳으로 이루어진 문자열을 입력받습니다.
필요한 접두사의 개수를 반환하는 함수를 작성합니다.
count 변수를 0으로 초기화합니다.
문자열의 첫 번째 문자의 빈도수를 계산합니다.
첫 번째 문자의 빈도수를 출력합니다. 이 값이 곧 문자열 접두사의 최대 출현 횟수입니다.
예제 코드
아래 프로그램은 위 해결 방법이 실제로 동작하는 모습을 보여줍니다.
#include <iostream>
using namespace std;
int findPrefixOccurence(string str){
char firstChar = str[0];
int countOccurrence = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == firstChar)
countOccurrence++;
}
return countOccurrence;
}
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
위 코드의 findPrefixOccurence() 함수는 문자열의 첫 문자를 기준으로 삼아 전체 문자열을 한 번 순회하며, 같은 문자가 나타날 때마다 카운트를 1씩 증가시킵니다. 예제 문자열 “xyyzxxyyzxyxx”에서 첫 문자 ‘x’는 총 6번 등장하므로 결과값은 6이 됩니다.
복잡도 분석
시간 복잡도: O(N) — 문자열의 길이 N만큼 딱 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 추가적인 메모리 없이 상수 공간만 사용합니다.