[백준, Java] 16120번 : PPAP

🔗 문제 링크

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

😮 문제 해결 방법

스택을 이용해서 문제를 해결했다.

‘P’가 들어오는 경우 스택에 저장하고, ‘A’가 들어오는 경우는 PPAP 문자열인지 판단해주었다.

‘A’가 들어오는 경우 PPAP 문자열인지 판단하기 위해 바로 다음 인덱스 문자가 ‘P’인지 판단하고 스택 사이즈가 2 이상 (스택에는 ‘P’만 들어감)인지 확인 후 스택을 두번 pop해 주었다.

결론적으로, 스택에서 pop된 문자 2개 PP와 현재 인덱스 A, 다음 인덱스 P가 되어 문자열 PPAP가 만들어지므로 다음 인덱스 ‘P’로 대체가 가능하다.

이외의 경우는 PPAP문자열을 P로 대체할 수 없으므로 “NP”를 리턴한다.

모든 PPAP 문자열이 P로 대체된다면, 마지막에는 처음 시작 문자인 P만 남기 때문에 스택 사이즈가 1이면 PPAP 아닌 경우는 NP를 리턴해주었다.

🚩 Java 코드

package com.algorithm.Baekjoon;

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

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

        String str = br.readLine();

        String rst = checkPPAP(str);
        System.out.println(rst);
        br.close();
    }

    private static String checkPPAP(String str) {
        Stack<Character> stack = new Stack<>();

        int index = 0;
        for (char c : str.toCharArray()) {
            if(c == 'P') stack.push(c);
            // A인 경우
            else {
                // A 다음 P인 경우 PPAP 성립
                // 다음 문자 확인 위해 인덱스 체크, PP삭제 위해 스택 사이즈 체크. 다음 문자 P인지 체크
                if(index < str.length() - 1 && stack.size() >= 2 && str.charAt(index+1) == 'P') {
                    stack.pop();
                    stack.pop();
                }
                // 이외의 경우 PPAP를 P로 대체할 수 없음
                else {
                    return "NP";
                }
            }
            index++;
        }

        return stack.size() == 1 ? "PPAP" : "NP";
    }
}