BOJ 16120 : PPAP [C++]

 

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

16120번: PPAP

 

문제 요약

문자열 $S$가 주어지면, $S$가 PPAP 문자열인지 확인하는 문제이다.

PPAP 문자열은 다음 두 가지 방법으로 정의된다.
- $P$는 PPAP 문자열이다.
- PPAP 문자열에서 $P$ 하나를 $PPAP$로 바꾼 문자열은 PPAP 문자열이다.

 

접근

문자열 $S$에서 차례대로 문자를 하나씩 꺼내서 $PPAP$가 만들어지면 그 부분을 $P$로 바꿔주는 방식으로 구현했다. 변수 $a$와 $p$를 선언하여 각각 현재까지 나온 $A$, $P$의 개수를 저장한다. 변수 $prev$를 선언하여 바로 전에 나온 글자가 연속하지 않은 $A$인지 확인할 수 있도록 구현했다.

꺼낸 문자가 $i$번째 문자라고 하자.$(0 \le i \le S.size - 1)$

크게 두 가지 경우로 나뉜다.

1. $i$번째 문자가 $P$인 경우

이 때는 두 가지 경우로 또 나눌 수 있다.

전에 나온 문자가 $A$이고, 현재까지 나온 $P$의 개수가 2 이상인 경우 : $PPAP$가 만들어진 것이므로 $PPAP$를 $P$로 만든다. (간접적으로 구현했다. $P$의 개수를 1 줄이고, $A$의 개수를 1 줄인 것과 동일하다.)

그렇지 않은 경우 : $prev$를 0으로 초기화하고, 현재까지 나온 $P$의 개수인 $p$를 1 증가시킨다.

2. $i$번째 문자가 $A$인 경우

바로 전에도 $A$가 나왔다면, $PPAP$가 나올 수 없으므로 $A$가 나오지 않은 것으로 친다.
바로 전에 $P$가 나왔다면, $A$가 정상적으로 나온 것이므로 a를 1 증가시켜주고, $prev$를 1로 초기화한다.

모든 문자 탐색이 끝난 후, 남은 문자는 오직 $P$하나여야 하므로 조건문으로 확인해준다.

 

#include <iostream>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int a = 0, p = 0, prev = 0;
	char s[1000000]{}, i;
	while (cin >> i) {
		if (i == 'P') {
			if (prev && p > 1) {
				p--;
				a--;
				prev = 0;
			}
			else {
				prev = 0;
				p++;
			}
		}
		else {
			if (prev)	prev = 0;
			else {
				a++;
				prev = 1;
			}
		}
	}
	if (a || p != 1)	cout << "NP";
	else	cout << "PPAP";
}