C++로 알파벳 순서를 이루는 부분 문자열 개수 구하기

길이가 n인 문자열이 주어졌다고 가정해 보겠습니다. 이 문자열에는 대문자만 포함되어 있습니다. 우리가 구해야 할 것은 각 문자가 알파벳 순서대로 연속해서 등장하는 부분 문자열의 개수이며, 부분 문자열의 최소 길이는 2여야 합니다.

예를 들어 문자열이 "REFJHLMNBV"라고 한다면, 조건을 만족하는 부분 문자열은 "EF"와 "MN", 총 2개입니다.

접근 방법

이 문제는 다음 단계를 따라 효율적으로 해결할 수 있습니다.

• 현재 위치 i에서 str[i] + 1(현재 문자의 바로 다음 알파벳)이 str[i+1]과 같은지 확인합니다.
• 같다면 결과값을 1 증가시킨 뒤, 알파벳 순서가 유지되는 동안 계속 앞으로 이동하며 문자열을 순회합니다.
• 순서가 깨지는 지점을 만나면 바깥 반복문으로 돌아가 다음 위치부터 다시 검사를 진행합니다.

이 방식은 각 문자를 한 번씩만 방문하므로 시간 복잡도는 O(n)으로 매우 효율적입니다.

예제 코드

#include<iostream>
using namespace std;
int countSubstr(string main_str) {
   int res = 0;
   int n = main_str.size();
   for (int i = 0; i < n - 1; i++) {
      if (main_str[i] + 1 == main_str[i + 1]) {
         res++;
         while (main_str[i] + 1 == main_str[i + 1]) {
            i++;
         }
      }
   }
   return res;
}
int main() {
   string str = "REFJHLMNBV";
   cout << "Number of substrings: " << countSubstr(str);
}

실행 결과

Number of substrings: 2