C++ STL을 활용한 길이 2의 고유한 연속 부분 문자열 개수 세기

개요

이 튜토리얼에서는 C++ STL(표준 템플릿 라이브러리)을 사용하여 문자열 내에서 길이가 2인 고유한 연속 부분 문자열의 개수를 세는 프로그램을 살펴봅니다.

하나의 문자열이 입력으로 주어지며, 우리의 목표는 이 문자열에서 길이가 2인 모든 고유한 부분 문자열을 찾아내고, 각 부분 문자열이 몇 번 등장하는지 함께 출력하는 것입니다.

접근 방법

핵심 아이디어는 간단합니다. 문자열을 처음부터 끝까지 순회하면서 인접한 두 문자를 하나의 쌍(pair)으로 묶습니다. 그리고 C++ STL의 map<pair<char, char>, int> 자료구조를 사용하여 각 문자 쌍의 등장 횟수를 저장합니다. map은 키를 기준으로 자동 정렬되므로, 결과도 사전순으로 깔끔하게 출력됩니다.

예제 코드

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

void calc_distinct(string str){
    map<pair<char,char>, int> dPairs;
    for (int i = 0; i < str.size() - 1; i++)
        dPairs[make_pair(str[i], str[i+1])]++;
    
    cout << "Distinct sub-strings with counts:\n";
    for (auto it = dPairs.begin(); it != dPairs.end(); it++)
        cout << it->first.first << it->first.second
             << "-" << it->second << " ";
}

int main(){
    string str = "abcacdcacabacaassddssklac";
    calc_distinct(str);
    return 0;
}

출력 결과

Distinct sub-strings with counts:
aa-1 ab-2 ac-4 as-1 ba-1 bc-1 ca-4 cd-1 dc-1 dd-1 ds-1 kl-1 la-1 sd-1 sk-1 ss-2

코드 설명

calc_distinct 함수는 문자열을 한 번씩 순회하면서 현재 문자 str[i]와 다음 문자 str[i+1]로 구성된 pair를 만들어 map에 삽입합니다. 동일한 쌍이 다시 나타나면 해당 값(value)이 자동으로 증가하여 등장 횟수가 누적됩니다.

모든 순회가 끝난 후에는 반복자(iterator)를 사용해 map의 내용을 출력합니다. 위 실행 결과에서 예를 들어 ac-4는 부분 문자열 "ac"가 원본 문자열에서 총 4번 등장했음을 의미합니다.

시간 복잡도

문자열의 길이를 N이라 할 때, 순회에 O(N)의 시간이 걸리고, map의 삽입 및 조회는 O(log N)이므로 전체 시간 복잡도는 O(N log N)입니다. 만약 정렬이 필요 없다면 unordered_map을 사용하여 평균적으로 O(N)까지 성능을 개선할 수 있습니다.