C++로 문자열에서 두 번째로 많이 등장하는 문자 찾기

이 문제에서는 문자열 str이 주어지며, C++로 문자열에서 두 번째로 많이 등장하는 문자를 찾는 프로그램을 작성하는 것이 목표입니다.

예시를 통한 문제 이해

입력

str = "abaacabcba"

출력

'b'

위 예시에서 문자 'a'는 5번, 'b'는 3번, 'c'는 2번 등장합니다. 따라서 가장 많이 등장하는 문자는 'a'이고, 두 번째로 많이 등장하는 문자는 'b'가 됩니다.

해결 접근 방법

문자열에서 두 번째로 많이 등장하는 문자를 찾으려면 각 문자의 등장 횟수를 저장하는 카운트 배열(charCount)을 활용해야 합니다. 이 배열을 이용해 최대 빈도(max)와 두 번째로 큰 빈도(secondMax)를 가진 문자를 찾아낸 뒤, 두 번째로 많이 등장하는 문자를 출력하면 됩니다.

구체적인 알고리즘은 다음과 같습니다.

1. 크기가 256인 배열을 선언해 문자열 내 모든 문자의 빈도를 저장합니다.
2. 문자열을 한 번 순회하면서 각 문자의 빈도를 카운트합니다.
3. 빈도 배열을 순회하며 최대 빈도 문자와 두 번째로 큰 빈도 문자를 조건에 따라 갱신합니다.
4. 두 번째로 많이 등장하는 문자를 결과로 반환합니다.

이 방식의 시간 복잡도는 O(n)이며, 고정 크기 배열만 사용하므로 공간 복잡도는 O(1)입니다.

솔루션 동작 과정 예제

#include <iostream>
#include <string.h>
using namespace std;
char findSecFreqChar(string str){
    int charFreq[256] = {0};
    for (int i = 0; i < str.length(); i++)
        (charFreq[str[i]])++;
    int maxFreq = charFreq[0], secFreq = charFreq[0];
    for (int i = 0; i < 256; i++){
        if (charFreq[i] > charFreq[maxFreq]){
            secFreq = maxFreq;
            maxFreq = i;
        }
        else if (charFreq[i] > charFreq[secFreq] &&
        charFreq[i] != charFreq[maxFreq])
        secFreq = i;
    }
    return secFreq;
}
int main(){
    string str = "tutorialspoint";
    char secFreqChar = findSecFreqChar(str);
    cout << "Second most frequent character of the string is" << secFreqChar;
    return 0;
}

출력 결과

Second most frequent character of the string is i

위 프로그램은 "tutorialspoint" 문자열에서 각 문자의 빈도를 계산합니다. 가장 많이 등장하는 문자는 3번 등장한 't'이며, 그다음으로 많이 등장한 문자 'i'가 결과로 출력됩니다.