[JAVA] 백준 16120번 : PPAP

 

---

 

• 생각

PPAP는 P로 바꿀 수 있다. 예) PPPAPAP는 PPPAPAP 굵은 부분을 P로 바꾸면 PPAP가 되니 PPAP 문자열이다.

 

기본적으로 이렇게 PPAP를 replace시켜 P로 바꿔주면 결과는?? 틀렸다고 뜬다.

이유는 PPAP를 P로 바꾸면서 또다시 PPPAPAP와 같은 문자열이 만들어질 수 있기 때문이다.

 

생각해낸 다른 방법은 반복문을 돌리면서 PPAP로만 만들어진 문자열인지 체크를 해주어야한다.

 

풀면서 생각해봤는데 현재까지 풀어본 그리디 문제는 정렬을 하면서 푸는 문제였다. 하지만 이 문제는 정렬을 해버리면 PPAP의 순서를 제대로 알아내기 어렵기 때문에 정렬을 하면 안된다. 그래서 그리디 문제이기보단 문자열 문제느낌이 더 강한것 같다.

 

• 코드

정답 코드 : 반복문을 돌리면서 PPAP로 만들 수 있는지 체크해 준다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static String ppap;
	static int count;

	public static void main(String[] args) throws Exception {
		SetData();
		SearchStringPPAP();
		System.out.println(ppap);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		ppap = br.readLine();
		count = 0;
	}
	
    public static void SearchStringPPAP() {
    	for(int i = 0; i < ppap.length(); i++) {
    		if(ppap.charAt(i) == 'P') {
    			count++;
    		} else {
    			// PPAP이면 PPAP는 P로 바꿀 수 있기 때문에 count를 -1만 해준다.
    			if(count >= 2 && ppap.length() > i + 1 && ppap.charAt(i+1) == 'P') {
    				count--;
    				i++;
    			} else {	// 현재 A인데 앞에 PP가 없으면 PPA가 되지 않기 때문에 NP를 출력
    				count = 0;
    				break;
    			}
    		}
    	}
    	
    	if(count == 1)
    		ppap = "PPAP";
    	else
    		ppap = "NP";
    }

}