C++로 문자열에서 처음 반복되는 문자 찾는 방법

문자열이 주어졌을 때, 가장 먼저 반복해서 등장하는 문자를 찾아야 하는 경우가 있습니다. 예를 들어 "Hello Friends"라는 문자열에는 'l'이 연달아 두 번 나타나므로, 첫 번째 반복 문자는 'l'입니다.

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

이 방식은 문자열 길이에 비례하여 한 번만 순회하기 때문에 시간 복잡도는 O(n), 사용하는 문자 종류가 제한적이라면 공간 복잡도 역시 O(1)로 간주할 수 있습니다.

예제 코드

#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

코드 설명

getFirstRepeatingChar 함수는 unordered_set에 지금까지 등장한 문자들을 저장합니다. 새로 읽은 문자가 이미 집합 안에 있다면 find 함수가 해당 위치를 반환하므로, 이를 통해 반복 여부를 판단할 수 있습니다. 만약 문자열 전체를 검사해도 반복 문자가 없다면 널 문자('\0')를 반환하여 결과가 없음을 알립니다.