백준 16120번 - PPAP (JAVA)

문제링크

 

 

문제 풀이 과정

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

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

 

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

 

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

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

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

 

 

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

 

전체 코드