문제

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를 출력한다.

---

1. 기본 아이디어 및 소스코드

1. P가 나오면 일단 pcount를 하나 증가시킨다.
2. A가 나오면, 앞에 P가 2개 이상 있어야하므로, pcount >= 2인지 확인해준다.
   1. A 바로 뒤의 글자가 P이면 pcount를 하나 내려준다.
   2. A 바로 뒤의 글자가 A라면 A가 연속해서 두 개 나오는 경우는 PPAP 문자열이 될 수 없으므로 NP출력 후 종료
3. 최종 결과가 pcount == 1이라면 PPAP 문자열이고, 아니면 아닌거다.

#include <iostream> #include <cstring> int main() { char str[1000001]; int pcount = 0; scanf("%s", str); for (int i = 0; i < strlen(str); i++) { if (str[i] == 'P') pcount++; else if (str[i] == 'A') { if (pcount >= 2 && str[i + 1] == 'P') { pcount--; i++; } else { printf("NP\n"); return 0; } } } if (pcount == 1) printf("PPAP\n"); else printf("NP\n"); }