[백준 16120] PPAP(Java)

문제 링크 : https://www.acmicpc.net/problem/16120

이 문제는 스택을 이용하여 풀 수 있습니다. 처음에 백트래킹으로 문자열의 모든 부분을 탐색하는 방식으로 진행했는데 메모리 초과가 발생했습니다. 조금 더 생각해보니 그리디 방식으로 앞에서부터 PPAP 문자열이 완성되면 바로바로 P로 치환해도 정답이 같기 때문에 스택으로 진행했습니다.

문자를 탐색하면서 스택에 담고, 스택의 사이즈가 4 이상일 경우 스택을 4번 pop해서 나온 문자열이 PPAP일 경우 스택에 P만을 추가하고 그 외의 경우 pop한 문자열을 다시 순서대로 스택에 추가합니다. 이 때 마지막 스택의 사이즈가 1이고 그 피크값이 P일 경우 PPAP이기 때문에 그 값을 출력합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static String PPAP = "PPAP";
    static Stack<Character> stack = new Stack<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        for(int i=0;i<str.length();i++){
            char curr = str.charAt(i);
            stack.add(curr);

            if(stack.size() >= 4){
                String tmp = "";
                for(int j=0;j<4;j++) tmp = stack.pop() + tmp;

                if(tmp.equals(PPAP)) stack.add('P');
                else for(int j=0;j<4;j++) stack.add(tmp.charAt(j));
            }
        }

        if(stack.size()==1 && stack.peek()=='P') System.out.println("PPAP");
        else System.out.println("NP");
    }
}