[C++] 백준 16120번 PPAP

문제

bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.

PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.

P는 PPAP 문자열이다.
PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.
예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.

문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.

입력

첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

출력

첫 번째 줄에 주어진 문자열이 PPAP 문자열이면 PPAP를, 아닌 경우 NP를 출력한다.

풀이

더이상 변환이 불가능할때까지 PPAP를 P로 변환시켜야한다. 물론 문자열을 직접 바꾸면 시간초과가 나기때문에 P의 개수를 기억했다 A이후 P가 나오면 P를 2개 줄이는 방식으로 구현해야한다.
문자열이 A로 끝나거나 이전P의 개수가 2개 미만인데 A가 나왔다면 PPAP문자열이 될 수 없다.
최종적으로 P가 하나만 남게 되면 주어진 문자열은 PPAP문자열이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

string str;

bool solve(){
  int cnt = 0;

  for (int i=0; i<str.length(); i++){
    if (str[i] == 'P'){
      cnt++;
    }
    if (str[i] == 'A'){
      if (i == str.length()-1) return false;
      if (str[i+1] == 'A') return false;

      if (str[i+1] == 'P'){
        if (cnt < 2) return false;
        else cnt -= 2;
      }
    }
  }
  return cnt == 1;
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> str;

  if (solve()) cout << "PPAP";
  else cout << "NP";
}