BOJ 16120 PPAP

https://www.acmicpc.net/problem/16120

16120번: PPAP

 

스택을 사용하여 풀 수 있는 문제입니다.

 

문자열의 P를 PPAP로 바꿀 수 있다는 말은, 달리 말하면 PPAP을 P로 바꾸어 원래 문자열을 복원할 수 있다는 뜻입니다. 문자열을 쭉 확인하며 스택에 문자들을 넣어준 뒤, 맨 마지막 네 문자가 PPAP라면 P로 바꾸는 과정을 반복하여 마지막에 스택에 P만 남아있다면 PPAP를, 아니라면 NP를 출력하면 됩니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    string str;
    cin >> str;

    n = str.length();

    stack<char> s;

    for (int i = 0; i < n; i++) {
      s.push(str[i]);
      if (s.size() >= 4) {
        char d = s.top();
        s.pop();
        char c = s.top();
        s.pop();
        char b = s.top();
        s.pop();
        char a = s.top();
        s.pop();

        if (a == 'P' && b == 'P' && c == 'A' && d == 'P') s.push('P');
        else {
          s.push(a);
          s.push(b);
          s.push(c);
          s.push(d);
        }
      }
    }

    int flag = 1;

    if (s.size() > 1 || s.top() != 'P') flag = 0;

    if (flag) cout << "PPAP" << endl;
    else cout << "NP" << endl;
  }

  return 0;
}