백준16120 PPAP

작성일 | In

문제 링크

  • http://icpc.me/16120

문제 출처

  • 2018년 서울대학교 프로그래밍 경시대회 div.1 C번
  • 2018년 서울대학교 프로그래밍 경시대회 div.2 G번

사용 알고리즘

  • 그리디

시간복잡도

  • O(n)

풀이

PPAP
ppap 문자열에서 p를 ppap로 치환해도 그 문자열은 ppap 문자열이다.
주어진 문자열이 ppap 문자열인지 판단하는 방법은 ppap를 모두 p로 치환해서 마지막에 p 혹은 ppap가 나오는지 확인하면 된다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
using namespace std;

int main(){
	string str; cin >> str;
	int idx = 0;
	string chk = "";
	for (int i = 0; i < str.length(); i++){
		chk += str[i];
		if (chk.length() >= 4){
			char a, b, c, d;
			d = chk.back(); chk.pop_back();
			c = chk.back(); chk.pop_back();
			b = chk.back(); chk.pop_back();
			a = chk.back(); chk.pop_back();
			string now = ""; now += a; now += b; now += c; now += d;
			if (now != "PPAP"){
				chk += now;
			}
			else{
				chk += "P";
			}
		}

		else if (chk == "PPAP"){
			cout << "PPAP"; return 0;
		}
		//cout << "tmp :: " << chk << "\n";
	}
	if (chk == "P" || chk == "PPAP"){
		cout << "PPAP"; return 0;
	}
	cout << "NP";
}