[스택] 백준 16120번 PPAP

16120번

PPAP

처음에는 벡터를 이용해 풀어봤는데 시간 초과가 나서 다시 풀어야했다.

#include<iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
int geniee;
vector<char> check(vector<char> inp){
    vector<char> new_inp;
    for(int i=0;i<inp.size();i++){
      //  cout << "start num is " << i << endl;
       if(i<=inp.size() - 3 && inp[i]=='P' && inp[i+1]=='P' && inp[i+2]=='A' && inp[i+3]=='P'){
       //    cout << "num is " << i << endl;
           new_inp.push_back('P');
           i+=3;
       } 
       else{
         //  cout << "else\n";
           new_inp.push_back(inp[i]);
       }
    }
    return new_inp;
}

int main(){
    string inp;

    cin >> inp; 
    vector<char> temp;
    for(int i=0;i<inp.size();i++){
        temp.push_back(inp[i]);
    }
    while(temp.size()>4){
       // cout << "going into check\n";
     temp=check(temp);   
    }
    if(temp.size()==1 && temp[0]=='P'){
        cout << "PPAP" << endl;
    }
    else{
        if(temp.size()==4 && temp[0]=='P' && temp[1]=='P' && temp[2]=='A' && temp[3]=='P'){
            cout << "PPAP" << endl;
        }
        else{
            cout <<"NP" << endl;
        }
    }
    // for(int i=0;i<temp.size();i++){
    //     cout << temp[i];
    // }
}

(물론 비효율적이기도 하고 꼭 맞는 것도 아니지만..)

아무리 생각해도 시간초과를 해결하는 방법은 자료구조를 활용하는 방법 뿐이라,,스택을 사용했다.

PPAP 자체를 보는 것은 너무 비효율적이고, A에 주목해야 했다.

PPAP 문자열은 결국 마지막에 P 로 끝나야 한다.

그 말은, A 가 나왔을 때 무조건 PPAP 를 만족해야 PPAP 문자열이다.

A를 앞에 남기고 뒤로 넘어간 순간 PPAP 문자열이 될 수 없다.

이 점을 생각해내기가 너무 오래걸렸고 어려워서 여기저기 참고해야 했다.

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

int main(){
    string inp;
    stack<char> pp;
    cin >> inp; 
    vector<char> temp; 
    int pcnt = 0;
    for(int i=0;i<inp.size();i++){
        if(inp[i]=='P'){
            pp.push(inp[i]);
            pcnt++;
        }
        else{
            if(pcnt >=2){
                if(inp[i+1]=='P'){
                    pcnt--;
                    i+=1;
                }
                else{
                    cout << "NP\n";
                    return 0;
                }
            }
            else{
                cout << "NP\n";
                return 0;
            }
        }
    }  
    if(pcnt==1){
        cout << "PPAP\n";
        return 0;
    }
    else{
        cout << "NP\n";
        return 0;
    }

}