C++로 문자열에서 가장 긴 연속 반복 문자 찾기

알파벳으로 이루어진 문자열이 하나 주어집니다. 이때 문자열 안에서 가장 길게 연속해서 반복되는 문자를 찾아야 합니다. 예시를 통해 자세히 살펴보겠습니다.

입력 − String[] = "abbbabbbbcdd"

출력 − b

설명 − 위 문자열에서 가장 긴 연속 구간은 문자 'b'입니다. 연속된 b의 개수는 4개입니다.

입력 − String[] = "aabbcdeeeeed"

출력 − e

설명 − 위 문자열에서 가장 긴 연속 구간은 문자 'e'입니다. 연속된 e의 개수는 5개입니다.

프로그램에 적용된 접근 방식

문자 배열 string1[]에는 알파벳 문자열이 저장됩니다.
maxRepeating(char str[], int n) 함수는 문자열과 그 길이를 입력받아, 가장 긴 연속 반복 구간을 이루는 문자를 반환합니다.
str[] 배열의 첫 번째 위치부터 마지막 위치까지 문자열을 한 번 순회합니다.
현재 문자 str[i]와 바로 다음 문자 str[i+1]이 같으면 현재 연속 횟수(maxC)를 1씩 증가시킵니다.
다른 문자가 나타나 연속 구간이 끊기면, 지금까지의 연속 횟수가 기존 최댓값(count)보다 큰지 확인하고, 더 크다면 최댓값과 해당 문자(repchar)를 갱신한 뒤 연속 횟수를 1로 초기화합니다.
모든 순회가 끝나면 repchar를 최종 결과로 반환합니다.

예제 코드

#include <iostream>

char maxRepeating(char str[], int n){
    int count = 0;
    char repchar = str[0];
    int maxC = 1;
    for (int i=0; i<n; i++){
        if (str[i] == str[i+1] && i < n-1)
            maxC++;
        else{
            if (maxC > count){
                count = maxC;
                repchar = str[i];
            }
            maxC = 1;
        }
    }
    return repchar;
}

int main(){
    char string1[] = "aaabbaacccddef";
    int N = 14;
    printf("Maximum Consecutive repeating character in string: %c", maxRepeating(string1, N));
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

Maximum Consecutive repeating character in string: a

이 알고리즘은 문자열을 딱 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리 없이 문제를 해결할 수 있습니다. 연속된 요소를 세는 이러한 패턴은 문자열 압축, 런렝스 인코딩(Run-Length Encoding) 등 다양한 문제에서 활용되므로, 접근 방식 자체를 잘 익혀두면 유사한 유형의 문제에도 쉽게 응용할 수 있습니다.