[백준 16120] PPAP [Java]

문제

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'로 축소하는(논리적으로) 방식으로 풀이했다.

우선, 문자열을 순회하며 'P'인 경우 'P'의 개수를 카운트 해주자.

 

만약 아래의 조건을 성립한다면 'PPAP'가 존재하므로 'P'로 축소할 수 있다

• 현재 문자가 'A'이다.
• 이전에 'P'가 2개 이상있다.
• 다음 문자가 'P'이다.

다음 문자까지 탐색대상으로 보고 'P'로 축소한다면, p (>= 2) + 1 - 2으로 결국 --p를 해주면 된다.

탐색 순서도 조절해주자.(++i)

만약 위 조건들을 성립하지 않는다면 그 문자열은 'PPAP 문자열'이 아니다. 탐색을 중단하자

추가로 주어진 문자열이 모두 'P'로 이루어진 문자열 또는 적절하게 'PPAP'가 들어간 예외에 대해서도 'PPAP 문자열' 인지 판단해야한다. 풀이의 아이디어대로 남은 p가 1보다 큰지 확인하자.

 

Stack 풀이는 가능은 하지만, LIFO이기 때문에 비효율적이다.(탐색 문자가 'P'인 경우 Stack의 길이가 3이상 이고, pop을 3번 한 결과가 'A', 'P', 'P' 인 경우 'PPAP 문자열' 판단 가능) 

---

소스코드

보기 

---

출처

16120번: PPAP