[백준 16120 JAVA] PPAP

 

 

 

스택을 활용하는 자료구조 문제

 

stack의 크기가 3이상이고, 새로 들어오는 토큰이 "P", 스택의 가장 위에 있는 토큰이 "A"일때 하나씩 꺼내며 검사를 시작한다.

스택의 상위 요소가 "PPA"였다면 (코드에서는 굳이 Reverse를 안해서 "APP"로 검사) "P"만 넣어주면 된다.

만약 아니라면 다시 원상복귀 시킨다

 

1차적으로 스택에 넣으며 검사를 했다면 그다음은 뒤에서부터 거꾸로 검사를 해야한다.

 (반례는 찾지 못했는데 뒤에서 검사를 해야 정답이 나왔다)

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine();
        Stack<Character> st = new Stack<Character>();
        for (int i = 0; i < str.length(); i++) {
            char temp = str.charAt(i);

            if (st.size() >= 3 && temp == 'P' && st.peek() == 'A') {
                StringBuilder stb = new StringBuilder();
                for (int re = 0; re < 3; re++) {
                    stb.append(st.pop());
                }
                if (!stb.toString().equals("APP")) {
                    for (int re = 2; re >= 0; re--) {
                        st.add(stb.charAt(re));
                    }
                }

            }
            st.add(temp);
        }
        while (st.size()>=4 && st.peek()=='P'){
            StringBuilder stb = new StringBuilder();
            for (int re = 0; re < 4; re++) {
                stb.append(st.pop());
            }
            if (!stb.toString().equals("PAPP")) {
                for (int re = 3; re >= 1; re--) {
                    st.add(stb.charAt(re));
                }
                break;
            }
            st.add('P');
        }

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