PPAP
문제 해석
- 주어진 문자열이 PPAP문자열인지 확인하는 문제입니다.
- P는 PPAP문자열입니다.
- PPAP 문자열에서 P하나를 PPAP로 바꾼 문자 또한 PPAP문자열입니다.
- N<= 10^6
설계(10)
- PPAP인 부분을 P로 바꾸게 하면 O(N^2)으로 시간초과가 납니다.
- 문제를 해결하기 위해서 stack 아이디어를 사용하였습니다. N개의 문자를 더해주면서 인덱스를 조정해주면 O(N)으로 해결할 수 있습니다.
구현(20)
코드
#include <iostream>
#define MAXN 1000000
using namespace std;
char stk[MAXN];
string s;
int idx = 0;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
for (int i = 0 ; i < s.length(); i++){
stk[idx++] = s[i];
if (idx >=4){
if (stk[idx-4] == 'P' && stk[idx-3] == 'P' && stk[idx-2] == 'A' && stk[idx-1] == 'P') idx -=3;
}
}
if (idx == 1 && stk[idx-1]=='P') cout << "PPAP\n";
else cout <<"NP\n";
return 0;
}
디버깅
- 인덱스처리가 미흡하여 디버깅을 통해 수정하였습니다.
- 인덱스가 1이고 스택에 남아있는 문자가 P이면 PPAP를 출력하도록 하였습니다.
제출결과
- 12ms
마무리
- 스택을 이용한 문자열 처리 문제였습니다. 일전에 풀어본 유형이라 어렵지 않게 구현하였습니다.