백준 16120 c++ "PPAP" -PlusUltraCode-

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

 

[필자 사고]

PPAP를 만나면 p로 바뀌는 어쩌면 탐욕적 알고리즘과 유사하다.

결과를 이용하여 역추적하는 느낌??

 

필자는 해당 문제를 stack 을 이용하여 문제를 해결했다. 

특정 idx를 설정하여 해당 문자열이 현재 어느 위치인지 각인 시켜줬다.

약간 구현 문제 같은 느낌이 들었다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

 

• 데이터 구조
  • stack<Node>를 사용하여 문자를 하나씩 처리하며 상태를 저장합니다.
  • Node는 문자와 해당 문자가 PPAP 패턴 중 몇 번째 위치인지를 나타내는 인덱스를 함께 저장합니다.
  • 예를 들어 P가 PPAP의 첫 번째 등장이라면 인덱스 1, 그 다음 P는 2, A는 3, 마지막 P는 4.
• 핵심 변수
  • flagIdx: 현재까지 발견한 PPAP 패턴의 진행 상태를 나타냅니다. 0부터 시작해서 4까지 증가합니다.
  • 예를 들어, 'P' → 'P' → 'A' → 'P' 순으로 들어오면 flagIdx는 4까지 올라가며 완전한 PPAP가 감지됩니다.
• 문자 처리 (pushStr 함수)
  • 각 문자를 하나씩 확인하면서 flagIdx에 따라 다음 문자가 올바른지를 검사하고 스택에 넣습니다.
  • 예외가 생기면 flagIdx를 초기화하여 다음 시도에 대비합니다.
• PPAP 패턴 발견 시 처리 (updateStack 함수)
  • 스택에서 최근 4개의 문자를 꺼내고, 이 PPAP 패턴 전체를 P로 치환합니다.
  • 다시 P를 넣을 때는, 스택의 최상단 상태에 맞춰 flagIdx를 조정합니다.
  • 이는 "PPAP"가 하나의 "P"로 대체되는 동작을 구현한 것입니다.
• 전체 실행 (Game_Start 함수)
  • 문자열을 입력받아 한 글자씩 처리합니다.
  • 처리 중에 flagIdx == 4가 되면, PPAP 패턴이 완성되었으므로 이를 대체하고 스택을 업데이트합니다.
  • 최종적으로 스택의 내용이 "PPAP" 또는 "P"이면 "PPAP" 출력, 아니면 "NP" 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
typedef pair<char, int> Node;
string str;
stack<Node> myStack;
int flagIdx;

void Print() {
	vector<char> resultArr;
	while (!myStack.empty()) {
		resultArr.push_back(myStack.top().first);
		myStack.pop();
	}

	reverse(resultArr.begin(), resultArr.end());
	string str = "";
	for (char ch : resultArr) {
		str += ch;
	}
	cout << str << '\n';
}

void pushStr(char ch) {
	if (flagIdx == 0) {
		if (ch == 'P') {
			
			myStack.push({ ch ,++flagIdx});
		}
		else {
			flagIdx = 0;
			myStack.push({ ch,flagIdx });
		}

	}
	else if (flagIdx == 1) {
		if (ch == 'P') {
			myStack.push({ ch ,++flagIdx });
		}
		else {
			flagIdx = 0;
			myStack.push({ ch,flagIdx });
		}
	}
	else if (flagIdx == 2) {
		if (ch == 'A') {
			myStack.push({ ch ,++flagIdx });
		}
		else  {
			myStack.push({ ch,flagIdx });
		}
	}
	else if (flagIdx == 3) {
		if (ch == 'P') {
			
			myStack.push({ ch ,++flagIdx });
		
		}
		else if (ch == 'A') {
			flagIdx = 0;
			myStack.push({ ch,flagIdx });
		}
	}

	
}
void updateStack() {
	for (int i = 0; i < 4; i++) {
		myStack.pop();
	}

	if (myStack.empty()) {
		myStack.push({ 'P',1 });
		flagIdx = 1;
	}
	else {
		flagIdx = myStack.top().second;
		pushStr('P');
	}	

}


void Game_Start() {
	cin >> str;
	flagIdx = 0;
	for (int i = 0; i < str.size(); i++) {
		
		pushStr(str[i]);
		if (flagIdx == 4) {
			updateStack();
		}
	}

	vector<char> resultArr;
	while (!myStack.empty()) {
		resultArr.push_back(myStack.top().first);
		myStack.pop();
	}

	reverse(resultArr.begin(), resultArr.end());
	string str = "";
	for (char ch : resultArr) {
		str += ch;
	}
	
	if (str == "PPAP" || str == "P")cout << "PPAP";
	else cout << "NP";
}

int main(void) {
	Game_Start();
}