C++로 문자열에서 첫 번째 고유 문자의 인덱스 찾기: 해시맵 활용 방법

문제 개요

주어진 문자열 s에서 반복되지 않는 첫 번째 고유 문자를 찾아 그 인덱스를 반환하는 것이 이번 문제의 목표입니다. 만약 고유한 문자가 하나도 존재하지 않는다면 -1을 반환합니다.

입력 예시 1

s = "tutorialspoint"

출력:

설명: 문자열 "tutorialspoint"에서 반복되지 않는 첫 번째 고유 문자는 'u'이며, 그 인덱스는 1입니다. 따라서 1을 결과로 반환합니다.

입력 예시 2

s = "aaasttarrs"

출력:

-1

설명: 문자열 "aaasttarrs"의 모든 문자('a', 's', 't', 'r')가 두 번 이상 등장하므로 고유한 문자가 존재하지 않습니다. 따라서 -1을 결과로 반환합니다.

문제 해결 접근 방식

이 문제는 해시맵(HashMap)을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 문자열의 모든 문자를 한 번씩 순회하면서, 각 문자를 키(key)로 하고 출현 횟수를 값(value)으로 하는 해시맵을 만드는 것입니다.

모든 문자의 출현 횟수를 저장하는 데는 O(n)의 선형 시간이 걸립니다. 이후 문자열을 다시 순회하면서 해시맵에서 해당 문자의 빈도를 확인하고, 빈도가 정확히 1인 문자(즉, 한 번만 등장하는 문자)를 만나면 그 인덱스를 즉시 반환하면 됩니다.

알고리즘 단계

문자열 s를 입력으로 받습니다.
정수형 함수 uniqueChar(string str)는 문자열을 입력받아 처음 등장하는 고유 문자의 인덱스를 반환합니다.
문자열을 순회하면서 각 문자와 그 출현 횟수를 저장하는 해시맵을 생성합니다.
빈도가 1인 문자를 발견하면 해당 문자의 인덱스를 반환합니다.
문자열에 고유한 문자가 전혀 없다면 -1을 반환합니다.

C++ 구현 예제

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

int uniqueChar(string str) {
    int ans = -1;
    unordered_map<char, int> mp;

    // 각 문자의 출현 횟수 계산
    for (int i = 0; i < str.size(); i++) {
        mp[str[i]]++;
    }

    // 빈도가 1인 첫 번째 문자의 인덱스 찾기
    for (int i = 0; i < str.size(); i++) {
        if (mp[str[i]] == 1) {
            ans = i;
            break;
        }
    }
    return ans;
}

int main() {
    string s = "tutorialspoint";
    cout << uniqueChar(s) << endl;
    return 0;
}

실행 결과

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

설명: 입력 문자열 "tutorialspoint"에서 고유한 문자는 'u', 'r', 'l'이며, 이 중 가장 먼저 등장하는 고유 문자 'u'의 인덱스는 1입니다. 따라서 출력값은 1이 됩니다.

복잡도 분석

시간 복잡도: O(n) — 문자열을 최대 두 번 순회합니다.
공간 복잡도: O(k) — 여기서 k는 서로 다른 문자의 개수입니다(영문 소문자 기준 최대 26).