[백준 16120] PPAP (C++)

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

문제

---

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

 

문제 풀이

---

스택을 이용하는 문제.

 

P가 PPAP 문자열이고, P를 PPAP로 바꾼 문자열도 PPAP 문자열이므로, PPAP를 다시 P로 되돌려 맨 마지막에 P만 남는지 확인한다.

문자열을 처음부터 끝까지 확인하며 스택에 넣는다. 스택의 최상단 4 문자가 PPAP라면 4 문자를 꺼낸 후 스택에 P를 push한다. PPAP를 찾을 때 저장하는 자료구조가 스택이므로 최상단 4 문자를 꺼내면 P-A-P-P 순서로 꺼내지는 것에 주의한다.

 

문자열의 현재 문자가 P이고, 스택의 사이즈가 4이상이면 최상단 4문자가 PPAP일 가능성이 있으므로 4 문자를 꺼낸다. 순서대로 PAPP가 만들어지면 P가 PPAP로 변경된 것이므로 P를 다시 스택에 넣는다. PAPP가 만들어지지 않으면 꺼낸 4문자를 다시 스택에 넣는다.

끝까지 탐색했을 때 스택에 P만 남아있다면 PPAP 문자열이고, 아니라면 PPAP 문자열이 아니므로 NP를 출력하면 된다.

 

아래는 코드.

#include <iostream>
#include <stack>
using namespace std;
stack<char> s;
stack<char> temp;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str;
	string makeString = "";
	cin >> str;
	for (int i = 0; i < str.length(); i++)
	{
		s.push(str[i]);
		if (str[i] == 'P' && s.size() >= 4)
		{
			makeString = "";
			for (int j = 0; j < 4; j++)
			{
				char current = s.top();
				makeString += current;
				s.pop();
				temp.push(current);
			}
			if (makeString == "PAPP")
			{
				s.push('P');
				for (int j = 0; j < 4; j++)
				{
					temp.pop();
				}
			}
			else
			{
				for (int j = 0; j < 4; j++)
				{
					s.push(temp.top());
					temp.pop();
				}
			}
		}
	}
	if (s.size() == 1 && s.top() == 'P')
	{
		cout << "PPAP";
	}
	else
	{
		cout << "NP" << "\n";
	}
	return 0;
}