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

C++ 분할 정복으로 풀어보는 K번 이상 반복되는 문자가 있는 가장 긴 부분 문자열

문제 개요

소문자로만 구성된 문자열 s가 주어졌을 때, 부분 문자열 T 내부의 모든 문자가 최소 k번씩 등장하도록 만족하는 가장 긴 부분 문자열의 길이를 구하는 것이 이 문제의 목표입니다.

예를 들어 문자열이 "ababbc"이고 k = 2라고 가정해 보겠습니다. 이때 가장 긴 부분 문자열은 "ababb"이며, 그 길이는 5입니다. 이 부분 문자열 안에는 'a'가 2번, 'b'가 3번 등장하기 때문에 조건을 충족합니다.

접근 방법: 분할 정복

이 문제는 분할 정복(Divide and Conquer) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • k번 미만으로 등장하는 문자가 하나라도 있다면, 그 문자를 포함하는 어떤 부분 문자열도 정답이 될 수 없습니다.
  • 따라서 해당 문자를 기준으로 문자열을 잘라낸 뒤, 각 조각에 대해 같은 과정을 재귀적으로 반복합니다.
  • k번 미만으로 등장하는 문자가 더 이상 없다면, 현재 문자열 전체가 조건을 만족하므로 그 길이를 곧바로 반환합니다.

알고리즘 단계

  1. 문자열 s와 정수 k를 인자로 받는 재귀 함수 longestSubstring()을 정의합니다.
  2. k가 1이면 모든 문자가 조건을 자동으로 만족하므로 문자열의 길이를 그대로 반환합니다.
  3. 문자열의 길이가 k보다 작으면 어떤 문자도 k번 등장할 수 없으므로 0을 반환합니다.
  4. 크기 26의 배열 c를 선언하고 -1로 초기화한 뒤, 문자열을 순회하며 각 알파벳의 등장 횟수를 셉니다.
  5. 등장 횟수가 k 미만인 첫 번째 문자(badChar)를 찾습니다. 모든 문자가 k번 이상 등장했다면 badChar는 '*'로 유지됩니다.
  6. badChar가 '*'라면 현재 문자열 전체가 유효하므로 문자열의 길이 n을 반환합니다.
  7. 그렇지 않다면 badChar를 구분자로 문자열을 분할하고, 각 부분 문자열에 대해 재귀 호출한 결과 중 최댓값을 정답으로 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector <string> splitString(string s, char x){
      string temp = "";
      vector <string> res;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == x){
            if(temp.size())res.push_back(temp);
            temp = "";
         }
         else temp += s[i];
      }
      if(temp.size())res.push_back(temp);
      return res;
   }
   int longestSubstring(string s, int k) {
      if(k == 1)return s.size();
      if(s.size() < k )return 0;
      vector <int> cnt(26, -1);
      int n = s.size();
      for(int i = 0; i < n; i++){
         if(cnt[s[i] - 'a'] == -1) cnt[s[i] - 'a'] = 1;
         else cnt[s[i] - 'a']++;
      }
      char badChar = '*';
      for(int i = 0; i < 26; i++){
         if(cnt[i] != -1 && cnt[i] < k){
            badChar = i + 'a';
            break;
         }
      }
      if(badChar == '*')return n;
      vector <string> xx = splitString(s, badChar);
      int ans = 0;
      for(int i = 0; i < xx.size(); i++)ans = max(ans, longestSubstring(xx[i], k));
      return ans;
   }
};
   main(){
   Solution ob;
   cout << ob.longestSubstring("ababbc", 2);
}

입력

"ababbc"
2

출력

5

동작 원리 살펴보기

입력 문자열 "ababbc"에서 각 문자의 등장 횟수는 a: 2회, b: 3회, c: 1회입니다. k = 2이므로 'c'는 조건을 만족하지 못하는 문자, 즉 badChar가 됩니다. 문자열을 'c'를 기준으로 나누면 "ababb"라는 조각이 남습니다. 이 조각에서는 a가 2번, b가 3번 등장하므로 모든 문자가 k번 이상 등장하며, 따라서 최종 답은 길이 5가 됩니다.

시간 복잡도

재귀 호출 시마다 문자열을 순회하며 문자 빈도를 계산하므로 한 단계당 O(n)의 시간이 소요됩니다. 분할은 서로 다른 알파벳 종류(최대 26개)가 제거되는 방식으로만 발생하므로 재귀 깊이는 최대 26으로 제한됩니다. 따라서 전체 시간 복잡도는 대략 O(26 × n) 수준이며, 공간 복잡도는 분할된 문자열을 저장하기 위해 O(n)입니다.