C++로 입력 문자열에서 가장 많이 등장하는 문자 찾기

이 문제에서는 소문자로만 구성된 입력 문자열이 주어지며, 우리의 과제는 문자열에서 가장 많이 등장하는 문자를 찾는 것입니다.

만약 등장 빈도가 같은 문자가 여러 개 있다면, 사전순으로 더 앞서는(lexicographically smaller) 문자를 출력해야 합니다.

문제 이해를 위한 예시

입력

string = "programming"

출력

위 예시에서 'g'와 'r'은 각각 2번씩 등장하지만, 사전순으로 'g'가 더 앞서므로 결과는 'g'가 됩니다.

해결 접근 방법

이 문제를 해결하기 위해 해싱(hash) 기법을 활용할 수 있습니다. 해싱이란 문자열을 한 번 순회하면서 각 문자의 등장 횟수를 배열에 기록하는 방법을 말합니다.

일반적으로 해시 배열의 크기는 256으로 할당하지만, 문자열이 ASCII 코드 0~127 범위의 문자만 포함한다면 크기 128의 해시 테이블을 사용할 수 있습니다. 또한 이 문제처럼 소문자만 다룬다면 알파벳 개수에 해당하는 크기 26의 배열만으로도 충분히 처리할 수 있어 메모리를 더욱 효율적으로 사용할 수 있습니다.

알고리즘

입력 문자열을 읽어 들입니다.
문자열에서 최다 등장 문자를 계산하는 함수를 생성합니다.
각 문자의 등장 횟수를 저장할 배열을 만들고 모든 값을 0으로 초기화합니다.
입력 문자열을 순회하며 문자별 등장 횟수 배열(count array)을 구성합니다.
최대 빈도값(max count)과 결과 문자(result)를 초기화합니다.
빈도 배열을 순회하면서 가장 큰 빈도를 가진 문자를 찾습니다.
최종적으로 해당 문자를 출력합니다.

배열을 인덱스 순서대로(즉, 'a'부터 'z' 순으로) 탐색하기 때문에 빈도가 같은 문자가 여러 개 있을 때 자연스럽게 사전순으로 앞선 문자가 선택됩니다.

구현 예제

아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#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

복잡도 분석

이 알고리즘의 시간 복잡도는 문자열 길이를 n이라 할 때 O(n)입니다. 문자열을 한 번 순회하여 빈도를 계산하고, 크기가 고정된 26개의 배열을 한 번 더 순회하기 때문입니다. 공간 복잡도는 알파벳 빈도 배열 크기에 해당하는 O(1)로 상수 공간을 사용합니다.