C++로 문자열에서 홀수 번 등장하는 문자 출력하기

이 문제에서는 사용자로부터 문자열 str을 입력받은 뒤, 해당 문자열 안에서 홀수 번 등장한 문자만 골라 출력해야 합니다.

문제를 해결하려면 먼저 문자열에 포함된 각 문자가 총 몇 번 나타나는지 빈도를 계산해야 합니다. 그다음, 등장 횟수가 홀수인 문자만 출력하면 됩니다.

예시를 통해 문제를 더 자세히 이해해 보겠습니다.

입력 : adatesaas
출력 : dte

설명 − 각 문자별 등장 빈도는 다음과 같습니다.

이 중 등장 빈도가 홀수인 문자는 d, t, e입니다.

알고리즘

이제 이 문제를 해결하기 위한 알고리즘을 단계별로 살펴보겠습니다.

1단계 : 문자열을 순회하면서 각 문자의 등장 횟수를 배열에 저장합니다.
2단계 : 빈도 배열을 순회하면서 등장 횟수가 홀수인 문자만 출력합니다.

예제 코드

위 알고리즘을 바탕으로 프로그램을 작성해 보겠습니다.

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

int main(){
    string str = "adatesaas";
    int n = str.length();
    int frequency[26];
    memset(frequency, 0, sizeof(frequency));

    // 1단계 : 문자열을 순회하며 각 문자의 등장 횟수 카운트
    for (int i = 0; i < n; i++)
        frequency[str[i] - 'a']++;

    // 2단계 : 빈도 배열을 순회하며 홀수 빈도의 문자만 출력
    for (int i = 0; i < 26; i++) {
        if (frequency[i] % 2 == 1) {
            cout << (char)('a' + i) << " ";
        }
    }
    return 0;
}

출력 결과

d t e

중복 출력을 피하는 팁

문자열을 다시 한번 순회하며 조건을 검사하는 방식도 가능하지만, 이 경우 동일한 문자가 여러 번 중복해서 출력될 수 있습니다. 위 예제처럼 크기 26의 빈도 배열을 알파벳 순서대로 순회하면 각 문자를 정확히 한 번씩만 검사하므로, 중복 없이 깔끔한 결과를 얻을 수 있습니다.

이 방법의 시간 복잡도는 문자열 길이를 n이라 할 때 O(n)이며, 추가로 사용되는 공간은 알파벳 개수에 해당하는 고정 크기 배열 하나뿐이므로 O(1)의 공간 복잡도를 가집니다.