[Java] 백준 16120번 : PPAP

문제

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

예제 입력 1

PPPAPAP

예제 출력 1

PPAP

예제 입력 2 

PPAPAPP

예제 출력 2

NP

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    private static BufferedReader br;
	private static String s;
	private static Stack<Character> stack=new Stack<>();
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		s=br.readLine();

		boolean ppap=true;	// PPAP 문자열 여부
		boolean isA=false;	// A문자가 앞에 나왔는지 여부
		for(int i=0;i<s.length();i++) {
			if(isA) {	// 이전 문자가 A였을 경우
				if(s.charAt(i)=='P') {	// 이번 문자가 P이면
					stack.add('P');	// 스택에 P를 하나 추가하고, isA를 다시 false 처리하고, 다음 문자 탐색
					isA=false;
					continue;
				}
				else {	// 이번 문자가 또 A이면
					ppap=false;	// PPAP 문자열이 아님
					break;
				}
			}
			if(s.charAt(i)=='P') stack.add('P');	// 이번 문자가 P이면 스택에 추가
			else {	// 이번 문자가 A이면
				if(stack.size()<2) {	// 스택에 저장된 P의 개수가 부족하면 PPAP 문자열이 아님
					ppap=false;
					break;
				} else {	// 스택에 저장된 P의 개수가 2개 이상이면 스택에서 2개 pop 하고, isA를 true 처리
					stack.pop();
					stack.pop();
					isA=true;
				}
			}
		}
		if(isA) ppap=false;	// 마지막 문자가 A인 경우 PPAP 문자열이 아님
        if(stack.size()>1) ppap=false;	// 최종적으로 P가 될 수 있어야 PPAP 문자열인데, 스택에 P가 1개보다 많으면 PPAP 문자열이 아님
		
		if(ppap) System.out.println("PPAP");
		else System.out.println("NP");
	}

}

첫번째로, 스택을 이용하여 PPAP 문자열 여부를 판단할 생각을 하기 어려웠습니다.

두번째로, PPAP 문자열의 정의에 대해 정확히 이해하지 못해서 왜 계속 오답이 나오는지 이해할 수 없었습니다.

 

우선 첫번째 경우, P가 나오면 스택에 저장하고, A가 나오면 스택에서 2개의 P를 빼냅니다.

이때 스택에 저장된 P의 개수가 모자라면 PPAP 문자열이 될 수 없습니다. 또한 A 다음에 오는 문자가 P가 아니면 PPAP 문자열이 될 수 없습니다. 만약 PPAP 문자열이 가능한 경우라면 스택에  P를 하나 추가해줍니다.

 

두번째 경우, 반례를 몇 가지 생각해보겠습니다.

1. P -> PPAP

2. PP -> NP

3. PPPP -> NP

4. PPAP -> PPAP

5. PPAPPAP -> PPAP

6. PPPAPAP -> PPAP

7. PPAPPAP ->PPAP

 

위 예에서 2, 3번의 경우를 잘 생각해보았더니 PPAP 문자열에 대한 정의를 바르게 이해할 수 있었습니다.