C++에서 문자열 내 문자와 빈도를 출현 순서대로 출력하는 방법

문제 개요

이 문제에서는 소문자로만 이루어진 문자열이 하나 주어지며, 문자열에 등장하는 각 문자의 빈도(출현 횟수)를 구해야 합니다. 여기서 중요한 조건은 결과를 문자가 문자열에서 처음 등장한 순서 그대로 출력해야 한다는 점입니다.

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

입력 : "jskdk"
출력 :
j 1
s 1
k 2
d 1

설명 − 문자열에서 j, s, d는 각각 1번씩, k는 2번 등장합니다. 따라서 위와 같은 결과가 출력됩니다.

접근 방법

이 문제를 해결하려면 문자열에 등장하는 각 문자의 출현 횟수를 세어야 합니다. 가장 직관적인 방법은 문자열을 순회하면서 각 문자의 빈도를 배열에 저장한 뒤, 저장된 값을 기반으로 문자와 빈도를 함께 출력하는 것입니다.

핵심 포인트는 이미 출력한 문자를 다시 출력하지 않도록 처리하는 것입니다. 특정 문자를 출력한 후 해당 문자의 빈도를 0으로 초기화하면, 이후 같은 문자를 다시 만났을 때 자동으로 건너뛰게 됩니다. 이렇게 하면 별도의 정렬 없이도 첫 등장 순서를 그대로 유지할 수 있습니다.

알고리즘

크기가 26인 배열을 생성하여 문자열 내 각 알파벳 소문자(a~z)의 빈도를 저장합니다.
문자열을 다시 순회하면서, 아직 출력되지 않은(빈도가 0이 아닌) 문자를 빈도와 함께 출력하고 해당 빈도를 0으로 설정합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str = "tutorialspoint";
    int n = str.size();
    int frequency[26];
    memset(frequency, 0, sizeof(frequency));
    for (int i = 0; i < n; i++)
        frequency[str[i] - 'a']++;
    for (int i = 0; i < n; i++) {
        if (frequency[str[i] - 'a'] != 0) {
            cout<<str[i]<<"\t"<<frequency[str[i] - 'a']<<"\n";
            frequency[str[i] - 'a'] = 0;
        }
    }
    return 0;
}

실행 결과

t 3
u 1
o 2
r 1
i 2
a 1
l 1
s 1
p 1
n 1

코드 동작 원리

첫 번째 반복문에서는 str[i] - 'a' 연산을 통해 각 문자를 0부터 25 사이의 인덱스로 변환하고, 해당 인덱스의 값을 증가시켜 빈도를 누적합니다. 두 번째 반복문에서는 문자열을 처음부터 다시 훑으면서 빈도가 0이 아닌 문자를 발견하면 문자와 빈도를 출력한 뒤 그 값을 0으로 만듭니다. 덕분에 중복된 문자는 이후 순회에서 무시되고, 각 문자는 첫 등장 시점의 순서로 정확히 한 번만 출력됩니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — 문자열을 두 번 순회하므로 선형 시간이 걸립니다.
공간 복잡도: O(1) — 크기가 고정된 26칸짜리 배열만 사용하므로 입력 크기와 무관하게 상수 공간을 차지합니다.