새로운 화난 학생이 없는지 최소 몇 분 후에 계산하는 C++ 프로그램

길이가 n인 문자열 S가 있고 'A' 또는 'P'라는 두 가지 유형의 문자만 있다고 가정합니다. 연속으로 n명의 학생이 있고, i번째 학생은 S[i] ='A'이면 화를 내고, 'P'이면 S[i]가 참을성이 있다고 말합니다. 지수 i의 화난 학생은 1분마다 지수 i+1의 참을성 있는 학생을 때릴 것이고, 마지막 학생은 화가 나더라도 아무도 때릴 수 없다. 참을성 있는 학생을 때리면 그 학생도 화를 낸다. 그 이후로 신입생이 화를 내지 않는 최소 시간을 찾아야 합니다.

따라서 입력이 S ="PPAPP"와 같으면 출력은 2가 됩니다. 왜냐하면 첫 번째 분 후에 문자열은 "PPAAP"이고 두 번째 분에는 "PPAAA"가 되고 새로운 학생은 다시 화를 내지 않기 때문입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of S
ans := 0, cnt = 0
for initialize i := n - 1, when i >= 0, update (decrease i by 1), do:
   if S[i] is same as 'P', then:
      (increase cnt by 1)
   Otherwise
      ans := maximum of ans and cnt
      cnt := 0
return ans

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

int solve(string S) {
   int n = S.size();
   int ans = 0, cnt = 0;
   for (int i = n - 1; i >= 0; i--) {
      if (S[i] == 'P') {
         cnt++;
      } else {
         ans = max(ans, cnt);
         cnt = 0;
      }
   }
   return ans;
}
int main() {
   string S = "PPAPP";
   cout << solve(S) << endl;
}

입력

PPAPP

출력

2