[G4] 백준 16120번 PPAP C++ 스택, 문자열

리뷰

 

https://www.acmicpc.net/problem/16120

스택을 활용하여 주어진 문자열이 PPAP 문자열인지 체크하는 문제

문제를 이해하기 좀 힘들었으나 그냥 PPAP를 P로 치환 할 수 있다는 조건이 있는 문제이다.

 

 

전역 변수

• s : PPAP문자열인지 검사할 문자열을 저장할 변수
• stack : 스택으로 사용할 문자열

 

함수

1. PPAP

void PPAP()

 

스택의 맨 뒤 문자열이 PPAP인지 체크하는 함수

1. 스택의 크기가 4이상, 스택의 맨 뒤 4글자가 "PPAP"라면 while루프를 계속 돌아준다.
2. while 조건이 참이라면 스택에서 4개의 요소를 pop해준다.
3. pop이 완료된 후에는 'P'를 스택의 맨 뒤에 삽입해 준다.

 

 

문제풀이

1. 문자열 s를 입력 받고, s의 크기만큼 for문을 개행해 준다.
2. stack에 문자열의 앞에서부터 각 문자를 추가해 준다.
3. 스택에 추가된 문자가 'P'라면 PPAP함수를 호출하여 스택에 "PPAP" 문자열이 존재하는지 검증해준다.
4. for문이 종료된 후 stack에 남은 문자열이 "P"라면 "PPAP"를, 아니라면 "NP"를 출력해 준다.

 

트러블 슈팅

1. 초기에 스택에 남은 A의 개수를 통해 "PPAP"문자열인지 판단을 했다가 78%에서 Fail을 받았다.
2. "PP" 나 "PPP" 등 스택이 "P"가 아닐 경우 Fail 처리가 됨을 알아 "P"가 아닌 경우 "NP"를 출력하니 AC를 받았다.

 

참고 사항

• 문자열 자체를 스택으로 사용하고, 이터레이터를 통해 스택의 맨 뒤 4가지 요소만 체크하였다.

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;

string s, stack;

void PPAP() {
	while (stack.size() >= 4 && string(stack.end() - 4, stack.end()) == "PPAP") {
		int len = 4;
		while (len--) stack.pop_back();
		stack += 'P';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	for (int i = 0; i < s.size(); ++i) {
		stack += s[i];
		if (s[i] == 'P') PPAP();
	}
	if (stack == "P") cout << "PPAP";
	else cout << "NP";
}