C++ 문자열에서 첫 번째 비반복 문자 찾기: 단일 순회 알고리즘

이 튜토리얼에서는 주어진 문자열에서 첫 번째 비반복 문자(중복되지 않는 문자)를 찾는 방법을 배워보겠습니다. 먼저 예시를 통해 문제를 이해해 보겠습니다.

입력 − tutorialspoint

출력 − u

문자열 "tutorialspoint"에서 't'는 세 번, 'o'와 'i'는 두 번 등장하지만, 가장 앞쪽에 위치하면서 딱 한 번만 등장하는 문자는 'u'입니다. 따라서 출력 결과는 'u'가 됩니다.

문제 해결 접근 방식

이 문제는 다음 단계를 거쳐 해결할 수 있습니다.

문자열을 초기화합니다.
각 문자의 빈도수와 인덱스를 저장할 맵(map)을 초기화합니다.
문자열을 순회하면서 각 문자의 빈도수를 계산하여 맵에 저장합니다.
동시에 해당 문자가 마지막으로 등장한 인덱스도 함께 저장합니다.
맵에 저장된 문자 빈도 정보를 순회합니다.
빈도수가 1인 문자들 중 인덱스가 가장 작은 문자를 찾아 출력합니다.

구현 예제

위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>
#include <map>
using namespace std;

void findDistinctCharacters(string random_string) {
    // 문자별 빈도수와 인덱스를 저장할 맵 초기화
    map<char, int[2]> chars;
    // 문자열을 순회하며 빈도수와 인덱스 기록
    for (int i = 0; i < random_string.size(); ++i) {
        chars[random_string[i]][0]++;   // 빈도수 증가
        chars[random_string[i]][1] = i; // 인덱스 저장
    }
    int char_index = INT_MAX;
    // 빈도수가 1인 문자 중 가장 앞선 인덱스 찾기
    for (auto item : chars) {
        if (item.second[0] == 1) {
            char_index = min(char_index, item.second[1]);
        }
    }
    // 결과 출력
    cout << random_string[char_index] << endl;
}

int main() {
    findDistinctCharacters("tutorialspoint");
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

동작 원리 정리

이 알고리즘은 크게 두 단계로 동작합니다. 첫 번째 단계에서는 문자열을 한 번 순회하면서 각 문자의 등장 횟수와 위치(인덱스)를 맵에 기록합니다. 두 번째 단계에서는 맵을 확인하여 빈도수가 정확히 1인 문자들을 찾고, 그중 인덱스가 가장 작은 문자, 즉 문자열에서 가장 먼저 등장하는 고유 문자를 선택합니다.

맵(std::map)은 내부적으로 키를 기준으로 정렬된 상태를 유지하지만, 이 코드에서는 인덱스를 직접 비교(min 함수 활용)하기 때문에 문자의 실제 위치를 기준으로 정확한 답을 구할 수 있습니다. 시간 복잡도는 O(n log n)이며, 여기서 n은 문자열의 길이입니다.

마무리

지금까지 C++에서 문자열의 첫 번째 비반복 문자를 찾는 방법을 알아보았습니다. 이 접근 방식은 빈도수 계산과 인덱스 추적을 결합하여 효율적으로 문제를 해결합니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.