백준 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

 

풀이

 

푸는 방법이 도저히 생각이 안나서 다른 사람 풀이들을 찾아봤다..

 

처음에는 PPAP를 P로 바꾸는 과정을 반복해서 마지막에 P만 남으면 되는 식으로 처리하는건가? 해서 

replaceAll로 PPAP를 P를 바꾸는 반복문을 돌렸는데

PPPPPPPPPPAP 형태로 나오면 문자열의 길이만큼 PPAP를 P로 바꾸는 과정이 반복되서 시간초과가 났다

 

풀이를 찾아보니 
1. 스택에 P를 추가하다가 A를 만나면 pop()을 두번해서 P를 두개 날리는 과정을 반복, 마지막에 스택에 P만 남아있으면 올바른 PPAP 문자열

2. 스택에 넣은 문자열이 뒤에서부터 4개를 봤을때 PPAP면 그걸 P로 바꾸는 방법이 있었다

 

1번. a를 만나고 다음 문자가 p면 ppap니 앞에 p 두개 날리는 방식

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        String str = br.readLine();

        for(int i=0; i<str.length(); i++) {
            if(str.charAt(i) == 'P') {
                stack.push('P');
            } else {
                if(stack.size() >= 2 && i!= str.length() -1 && str.charAt(i+1) == 'P') {
                    stack.pop();
                    stack.pop();
                } else {
                    System.out.println("NP");
                    return;
                }
            }
        }
        if(stack.size() == 1) {
            System.out.println("PPAP");
        } else {
            System.out.println("NP");
        }
    }
}

 

2번. 뒤에 4개를 확인한 후 PPAP가 맞으면 len을 -3해버려서 p만 남게하는 방법

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        char[] input = in.next().toCharArray();
        char[] rewind = new char[input.length];
        int len = 0;
        for (char ch : input) {
            rewind[len++] = ch;
            if (len >= 4 && rewind[len - 1] == 'P' && rewind[len - 2] == 'A'
                    && rewind[len - 3] == 'P' && rewind[len - 4] == 'P')
                len -= 3;
        }
        System.out.println(len == 1 && rewind[0] == 'P' ? "PPAP" : "NP");
    }
}