Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 문자열의 중복 문자 찾기 및 출력하는 방법

문제 개요

이 문제에서는 하나의 문자열이 주어지며, 해당 문자열 안에서 중복해서 나타나는 모든 문자와 각 문자가 등장한 횟수를 찾아 출력해야 합니다.


예시로 이해하기

입력:
TutorialsPoint

출력:
t (3)
o (2)
i (2)

설명: 각 문자의 출현 빈도는 다음과 같습니다.

  • t → 3회
  • u → 1회
  • o → 2회
  • r → 1회
  • i → 2회
  • a → 1회
  • s → 1회
  • n → 1회

해결 접근 방법

이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.

  1. 문자열을 처음부터 끝까지 순회하면서 각 문자의 출현 횟수를 계산합니다.
  2. 계산된 빈도 값을 크기 256의 정수 배열에 저장합니다. (ASCII 문자 집합 전체를 커버하기 위함입니다.)
  3. 배열을 순회하면서 빈도가 1보다 큰 문자만 골라 해당 문자와 출현 횟수를 함께 출력합니다.

이 방식은 시간 복잡도 O(n)으로 매우 효율적이며, 추가 메모리는 고정 크기(256개 정수)의 배열만 필요하므로 공간 복잡도도 O(1)로 일정합니다.


C++ 구현 예제

# include <iostream>
using namespace std;
# define NO_OF_CHARS 256

class duplicate_char{
    public :
    // 문자열의 각 문자 빈도를 계산하는 함수
    void charCounter(char *str, int *count){
        int i;
        for (i = 0; *(str + i); i++)
        count[*(str + i)]++;
    }

    // 중복 문자를 출력하는 함수
    void printDuplicateCharacters(char *str){
        int *count = (int *)calloc(NO_OF_CHARS, sizeof(int));
        charCounter(str, count);
        int i;
        for (i = 0; i < NO_OF_CHARS; i++)
            if(count[i] > 1)
                printf("%c\t\t %d \n", i, count[i]);
        free(count);
    }
};

int main(){
    duplicate_char dupchar ;
    char str[] = "tutorialspoint";
    cout<<"문자열의 중복 문자\n";
    cout<<"문자\t\t횟수\n";
    dupchar.printDuplicateCharacters(str);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

문자열의 중복 문자
문자    횟수

i       2
o       2
t       3

코드 설명

charCounter 함수: 문자열의 끝(NULL 문자)에 도달할 때까지 한 글자씩 읽으면서, 해당 문자의 ASCII 코드를 인덱스로 사용해 count 배열의 값을 1씩 증가시킵니다.

printDuplicateCharacters 함수: calloc을 사용해 크기 256의 count 배열을 0으로 초기화한 뒤, charCounter로 빈도를 계산합니다. 이후 배열 전체를 확인하여 빈도가 1을 초과하는 문자만 화면에 출력하고, 마지막에 free()로 동적으로 할당한 메모리를 해제하여 메모리 누수를 방지합니다.

이처럼 ASCII 코드 값을 인덱스로 활용하는 기법은 문자 빈도 계산 문제에서 널리 사용되는 효율적인 패턴이므로, 유사한 문제(예: 첫 번째 반복 문자 찾기, 애너그램 판별 등)에도 응용할 수 있습니다.