[백준 16120] PPAP

PPAP 16120

유형

스택
자료구조

풀이

스택을 이용한 풀이는 항상 바로 안떠오르는 것 같다. 스택을 이용하면 쉽게 풀이할 수 있다.

문제의 규칙은 p로 시작해서 p -> ppap로 바꾸는 과정에서 생기는 모든 문자열을 ppap문자열이라고 정의한다. p도 ppap 문자열

입력 문자열을 처음부터 stack에 넣으면서 크기가 4이상이면 4개를 꺼내서 ppap인지 확인하고 ppap이면 p로 바꾸어 stack에 넣어준다.

연산 마지막 결과가 p이면 PPAP를 출력하고 아니면 NP를 출력

코드

#include <bits/stdc++.h>
using namespace std;

string str;
vector<char> v;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> str;
	v.push_back(str[0]);
	for (int i = 1; i <= str.size(); i++) {
		while (v.size() >= 4) {
			char a = v.back(); v.pop_back();
			char b = v.back(); v.pop_back();
			char c = v.back(); v.pop_back();
			char d = v.back(); v.pop_back();

			if (d == 'P' && c == 'P' && b == 'A' && a == 'P') {
				v.push_back('P');
			}
			else {
				v.push_back(d); v.push_back(c); v.push_back(b); v.push_back(a);
				break;
			}
		}
		if (i == str.size()) break;
		v.push_back(str[i]);
	}

	if (v.size() == 1 && v[0] == 'P') cout << "PPAP";
	else cout << "NP";

	return 0;
}