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

C++로 풀어보는 문자 교환 후 가장 긴 반복 문자 부분 문자열 구하기

문자열 text가 주어지고, 이 문자열 안에서 두 개의 문자를 딱 한 번 서로 교환(swap)할 수 있다고 가정해 봅시다. 이때 동일한 문자가 반복되는 가장 긴 부분 문자열(substring)의 길이를 구하는 것이 문제의 목표입니다.

예를 들어 입력이 "ababa"라면 결과는 3이 됩니다. 첫 번째 b와 마지막 a를 교환하거나, 마지막 b와 첫 번째 a를 교환하면 가장 긴 반복 문자열이 "aaa"가 되어 길이가 3이기 때문입니다.

접근 방법 및 알고리즘

이 문제는 슬라이딩 윈도우(sliding window) 기법과 문자 빈도수 계산을 조합하여 효율적으로 해결할 수 있습니다. 구체적인 해결 단계는 다음과 같습니다 −

  • 맵 cnt를 정의하고, ret := 1, j := 0, n := text의 크기, v := 0으로 초기화합니다. 집합(set) x를 정의하고, 각 문자의 전체 등장 횟수를 저장할 또 다른 맵 m을 생성합니다.

  • a := '*'와 b := '*'로 설정합니다. 여기서 '*'는 아직 윈도우 내에 두 번 이상 등장한 문자가 없음을 나타내는 임시 값입니다.

  • i를 0부터 n-1까지 반복합니다 −

    • cnt[text[i]]를 1 증가시킵니다.

    • text[i]를 집합 x에 삽입합니다.

    • 만약 cnt[text[i]]가 2라면 − a가 '*'이면 a := text[i]로 설정하고, 그렇지 않으면 b := text[i]로 설정합니다.

    • 만약 a와 b가 모두 '*'가 아니거나 집합 x의 크기가 2보다 크다면 − cnt[text[j]]를 1 감소시킵니다. 이때 cnt[text[j]]가 1이 되면 text[j]가 a와 같은 경우 a := '*'로, 그렇지 않으면 b := '*'로 설정합니다. 이후 cnt[text[j]]가 0이 되면 집합 x에서 text[j]를 삭제하고 j를 증가시켜 윈도우를 축소합니다.

    • greater를 cnt[a] > cnt[b]인 경우에는 a로, 그렇지 않으면 b로 설정합니다.

    • 집합 x의 크기가 1이거나 m[greater] – cnt[greater]가 0이 아니라면, 즉 윈도우 바깥에 동일한 문자가 더 존재한다면 − ret := max(ret, i – j + 1)로 갱신합니다.

    • 그렇지 않으면 − ret := max(ret, i – j)로 갱신합니다.

  • 최종적으로 ret을 반환합니다.

핵심 아이디어는 윈도우 안에 서로 다른 문자가 최대 2종류만 존재하도록 유지하는 것입니다. 그중 더 많이 등장한 문자를 기준으로 삼되, 해당 문자가 문자열 전체에 더 남아 있어 교환으로 이어 붙일 수 있는 경우(m[greater] - cnt[greater] != 0)에는 길이를 하나 더 늘릴 수 있습니다.

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다 −

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxRepOpt1(string text) {
      int ret = 1;
      map <char, int> cnt;
      int j = 0;
      int n = text.size();
      int v = 0;
      set <char> x;
      map <char, int> m;
      for(int i = 0; i < text.size(); i++)m[text[i]]++;
      char a = '*', b ='*';
      for(int i = 0; i < n; i++){
         cnt[text[i]]++;
         x.insert(text[i]);
         if(cnt[text[i]] == 2){
            if(a == '*'){
               a = text[i];
            }else{
               b = text[i];
            }
         }
         while(a != '*' && b != '*' || x.size() > 2){
            cnt[text[j]]--;
            if(cnt[text[j]] == 1) {
               if(text[j] == a) {
                  a ='*';
               }else{
                  b = '*';
               }
            }
            if(cnt[text[j]] == 0) x.erase(text[j]);
            j++;
         }
         char greater = cnt[a] > cnt[b] ? a : b;
         if(x.size() == 1 || m[greater] - cnt[greater]){
            ret = max(ret, i - j + 1);
         }else{
            ret = max(ret, i - j);
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.maxRepOpt1("ababa"));
}

입력

"ababa"

출력

3