[백준/BOJ] 16120. PPAP [Gold 3]

16120. PPAP

문제출처 : https://www.acmicpc.net/problem/16120

code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    int i, len = 0, sp = 0;
    string str;
    char stk[1000001] = { 0 };
    cin >> str;
    len = str.length();

    for (i = 0; i < len; i++)
    {
        stk[sp] = str[i];
        sp++;
        if (sp > 2 && stk[sp-1] == 'P' && stk[sp - 2] == 'A' && stk[sp - 3] == 'P' && stk[sp - 4] == 'P')
            sp -= 3;
    }

    if (sp==1 && stk[0]=='P')
        cout << "PPAP" << '\n';
    else
        cout << "NP" << endl;

    return 0;
}

이번문제는 이해가 그렇게 어려운건 아니였는데, 구현하는데 시간이좀 걸렸다.
사실 그렇게 어려운건아닌데, 웬지 뭐가 계속 막히더라ㅠㅠ
다만 ppap문자열이라는 표현이 애매해서 좀 헷갈렸다.
P는 PPAP문자열로 바꿀수있고, PPAP문자열은 P로 바꿀 수 있다.
그래서 P는 PPAP문자열이라고 되어있는데, 중요한건 PP나 PPP처럼
PPAPPPAP, PPAPPPAPPPAP로 바꿀수있는문자열은 PPAP문자열이 아니다.

뭔소리냐면 결과로 PPAP문자열을 출력하려면 P를 출력해야한다는 뜻이다. 난 PP도 PPAP문자열인줄 알았는데 아니더라.

알고리즘은 간단한데,
스택자료구조를 써도되고 굳이 안쓰고 문자열 비교만해도 된다. 나는 인덱스 접근을 쉽게하려고 배열에 스택을 구현했다.

문자열을 입력받고, 스택에 넣어주고, 마지막 4글자가 PPAP이면 스택포인터를 감소시켜 (배열이라 POP을할순없으니) 압축해주는 식으로 짯다.