Logo냥냠감자기술 블로그
Skip to Content
AlgorithmGreedy (14)PPAP
작성일: 2024-01-12

문제

백준 16120 - PPAP 

  • 난이도: 골드4
  • 알고리즘: 그리디, 스택

코드

#include <iostream> #include <vector> using namespace std; bool checkPPAP(vector<char>& lets) { if(lets.size()<4) { return false; } string target="PPAP"; for(int i=lets.size()-4; i<lets.size(); i++) { if(lets[i]!=target[i-(lets.size()-4)]) { return false; } } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string input; cin>>input; vector<char> temp; for(int i=0; i<input.size(); i++) { temp.push_back(input[i]); while(checkPPAP(temp)) { for(int i=0; i<4; i++) { temp.pop_back(); } temp.push_back('P'); } } if(temp.size()==1 && temp[0]=='P') { cout<<"PPAP"; } else { cout<<"NP"; } }

회고

그리디를 공부하는 중이었는데 막상 해결해보니 그리디보단 스택을 이용해 해결한 것 같다. 스택을 활용한 유명한 문제인 괄호 검사 등의 문제가 떠오르는 문제였다. 문제에서 제시한 것과 반대로 주어진 문자열을 원본으로 바꾼 후 원본 문자열이 P와 동일한지 검사하는 방식으로 문제를 해결했다.