[BOJ][Java] 16120: PPAP

알고리즘 정리

이 문제는 문자열 내 "PPAP" 패턴을 만나면 "P" 하나로 줄일 수 있다는 규칙에 따라,

입력 문자열이 "PPAP문자열" 인지 판단하는 문제이다.

 

문제 접근 방식

처음부터 문자열을 직접 PPAP → P 로 바꿔가는 건 문자열이 겹치거나 중첩되는 경우 복잡해진다.

따라서 문자열을 왼쪽부터 순차적으로 스택에 쌓으면서 스택의 마지막 4글자가 PPAP 이면 그것을 "P"로 축약하는 방식을 선택했다. 

 

주요 단계: 

 

1. 문자열 입력 받기
2. 한 글자씩 스택에 push
3. 스택 마지막 4글자가 "PPAP"이면 → pop 4번 → push 'P'
4. 반복
5. 마지막에 스택이 'P' 하나라면 → "PPAP" 문자열, 아니라면 "NP"

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        Stack<Character> stk = new Stack<>();

        int len = input.length();
        for (int i = 0; i < len; i++) {
            char c = input.charAt(i);
            stk.push(c);

            if (stk.size() >= 4) {
                int sz = stk.size();
                if (stk.get(sz - 4) == 'P' &&
                    stk.get(sz - 3) == 'P' &&
                    stk.get(sz - 2) == 'A' &&
                    stk.get(sz - 1) == 'P') {

                    for (int j = 0; j < 4; j++) {
                        stk.pop();
                    }
                    stk.push('P');
                }
            }
        }

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