이번 문제는 Greedy 알고리즘을 통해 해결하였다. PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열이 PPAP가 된다는 정의에서 이해가 조금 필요했다.

이 정의를 간단한 예시들로 정리해보면 PPAP -> PPAPPAP(1번 P가 PPAP가 된 경우), PPPAPAP(2번 P가 PPAP가 된 경우), PPAPPAP(3번 P가 PPAP가 된 경우)로 변할 수 있고, 이 문자열 모두 PPAP에 해당한다는 것이다.

규칙을 찾는데 시간이 조금 걸렸다.

• A가 반드시 있어야 한다.
• 앞에서부터 P가 2개 이상 존재한 뒤에 A가 있어야 한다.
• A는 2번 연속으로 나올 수 없다.

규칙을 바탕으로 다음과 같이 해결하였다.

• 문자열이 P라면 st벡터에 P를 넣고 true를 반환하도록 한다.
• 문자열 길이만큼 검사를 진행한다.
• 문자열의 현재 인덱스에 해당하는 문자가 P일 경우, st벡터에 push_back('P') 해준다.
• 문자열의 현재 인덱스가 P가 아니고, st에 들어간 P가 2개 이상이고, 다음 인덱스에 해당하는 문자가 P일 때, st벡터에서 P 2개를 pop_back() 해준다.
• 이 외의 경우에는 false를 반환한다.
• 문자열 길이만큼 무사히 검사를 마치면 true를 반환한다.

xcode에서는 잘 실행됐지만 백준에 제출을 하니 70%대에서 오답처리 되었다. 반례를 생각하다가 PPPP는 PPAP가 아니라는 것을 생각하게 되었다. 본인이 작성한 코드에서는 PPPP도 true로 반환되기 때문에 오답처리된 것이었다.

• PPPP를 NP로 출력시키기 위해 Solution함수 마지막에 st에 들어간 P의 길이를 확인하여 P가 1개라면 true를, 1개가 아니라면 false를 반환하도록 하였다.
  PPAP -> st:+P, +P, -P, -P, +P st.size()=1
  PPPAPAP -> st:+P, +P, +P, -P, -P, +P, -P, -P, +P st.size()=1
  PPPP -> st: +P, +P, +P, +P st.size()=4

Code

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string ppap;
vector<int> st;

void Input(){
    cin>>ppap;
}

bool Solution(){
    if(ppap.size()==1&&ppap.front()=='P'){
        st.push_back('P');
    }
    else{
        for(int i=0; i<ppap.size(); i++){
            if(ppap[i]=='P'){
                st.push_back('P');
            }
            else if(st.size()>=2&&ppap[i+1]=='P'){
                st.pop_back();
                st.pop_back();
            }
            else{
                return false;
            }
        }
    }
    if(st.size()==1)
        return true;
    else
        return false;
}

void Solve(){
    if(Solution())
        cout<<"PPAP"<<endl;
    else
        cout<<"NP"<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solve();
    return 0;
}