백준 16120번 - PPAP (JAVA)

문제링크

 

 

문제 풀이 과정

문자열 일부분에 PPAP 가 있을 때 이 문자열을 P 로 치환을 하여 마지막에 문자열 P 하나만 남아 있다면 이 문자열은 PPAP 문자열이다. 

처음에는 이 문제를 문자열을 배열로 변환한 뒤 스택을 이용하여 풀었더니 시간초과가 되었다.

 

문자열을 배열로 변환하지 않고 문자열의 인덱스를 이용하여 문제를 풀었더니 해결되었다.

 

문자열에서 P 가 나오면 P 의 갯수를 카운트를 해준다. 이것을 A 가 나올때까지 카운트 해준다.

A 가 나왔을 때 P 의 갯수가 2개 이상이며, 다음 문자열이 P 일때만 PPAP 문자열이 되므로, P 의 수를 한개 줄여주고 문자열의 인덱스를 증가시킨다.

여기서 P 의 갯수를 한개 줄이는 PPAP 는 다시 P 로 치환되기때문에 다시 P 가 추가 된다. 결국 -2 + 1 = - 1 이 된다.

 

 

문제 해결할때 도움이 되었던 반례이다.

 

전체 코드

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	public class Main {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str = br.readLine();
	int pCnt = 0;
	boolean check = true;
	for (int i = 0; i < str.length(); i++) {
	char cur = str.charAt(i);
	if(cur == 'P'){
	pCnt++;
	}
	else if(cur == 'A' && pCnt >= 2){
	if(i < str.length() - 1 && str.charAt(i + 1) == 'P'){
	pCnt--;
	i++;
	}
	}
	else{
	check = false;
	break;
	}
	}
	if(pCnt == 1 && check){
	System.out.println("PPAP");
	}
	else{
	System.out.println("NP");
	}
	}
	}

view raw ppap.java hosted with ❤ by GitHub