C++로 문자열에서 가장 먼저 반복되는 문자 찾는 방법

문자열이 하나 주어졌을 때, 그중 가장 먼저 반복되는 문자를 찾는 문제를 생각해 보겠습니다. 예를 들어 문자열이 "Hello Friends"라면, 첫 번째 반복 문자는 'l'입니다. 'l'이 연달아 두 번 나타나기 때문입니다.

이 문제는 해싱(hashing) 기법을 사용하면 효율적으로 해결할 수 있습니다. 해시 집합(hash set)을 하나 생성한 뒤, 문자열의 각 문자를 왼쪽부터 차례대로 검사합니다. 해당 문자가 아직 집합에 없다면 삽입하고, 이미 존재한다면 그 즉시 그 문자를 반환하면 됩니다.

알고리즘 동작 원리

해시 기반 탐색은 평균적으로 O(1)의 시간 복잡도를 가지므로, 전체 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 공간 복잡도 역시 최악의 경우 모든 문자를 저장해야 하므로 O(n)입니다.

C++ 구현 예제

#include<iostream>
#include<unordered_set>
using namespace std;

char getFirstRepeatingChar(string &s) {
    unordered_set<char> hash;
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        if (hash.find(c) != hash.end())
            return c;   // 이미 존재하는 문자 → 반복 문자
        else
            hash.insert(c); // 처음 보는 문자 → 삽입
    }
    return '\0'; // 반복 문자가 없는 경우
}

int main() {
    string str = "Hello Friends";
    cout << "First repeating character is: " << getFirstRepeatingChar(str);
}

실행 결과

First repeating character is: l

코드 설명

• unordered_set<char>을 사용해 지금까지 등장한 문자들을 저장합니다.
• 각 문자에 대해 find()로 집합 내 존재 여부를 확인합니다.
• 이미 존재하는 문자를 만나면 즉시 반환하므로, 항상 첫 번째로 반복되는 문자가 결과가 됩니다.
• 반복 문자가 전혀 없다면 널 문자 '\0'을 반환하여 종료 조건을 나타냅니다.

이 방식은 이중 반복문을 사용하는 단순 비교 방식(O(n²))보다 훨씬 빠르며, 문자열이 길어질수록 그 성능 차이가 더욱 커집니다.