BOJ 16120 : PPAP

풀이 요약

그리디 문제

풀이 상세

1. $PPAP$ 라는 문자열은 $A$ 를 기준으로, 앞에 $P$ 가 2개, 뒤에 $P$ 가 1개인 경우의 문자열을 의미한다.
2. 만약 임의의 문자열에 $P$ 의 개수를 세면서 반복문을 실행했을 경우, 현재 $A$ 문자에서 $P$ 가 2개이상이며, 뒤의 문자 역시 $P$ 라면 $PPAP$ 라는 부분 문자열이 있다는 것이 증명된다.
3. 찾은 부분 문자열 $PPAP$ 를 $P$ 로 치환한다면, 현재까지 총 3개인 $P$ 의 갯수를 하나로 줄이는 것이다.
4. 탐색 중 다음과 같은 경우는 절대 $PPAP$ 가 나올 수 없다.
   • $P$ 의 갯수가 2개 이상이 채워지지 않는 상황에서 $A$ 가 찾아지는 경우
   • 모든 탐색을 끝마쳤을 때 남은 $P$ 의 갯수가 1이 아닌 경우
5. $false$ 의 경우가 나타나지 않은체 모든 탐색이 완료되었으며, 현재 남은 $P$ 의 갯수가 1인 경우가 $PPAP$ 에 해당하는 문자열이 된다.

배운점

• 재귀로 쉽게 풀거라 생각하고 했다가 메모리 초과가 났다. 콜 스택은 10000번 이상 되어서 그런가 생각하고 스택으로 만들었더니 역시 동일하게 메모리 초과가 일어났다. sutstr 메서드 때문인건지 모르겠으나, 아니면 idx 를 0 으로 초기화하여 반복해서 메모리 초과가 난건지 모르겠다. (일단 substr 이 문제라고 생각하고 있다. idx 가 문제라면 시간초과를 불러올 것이다.)
• C++ 에서 cout << 시 삼항 연산자를 사용했더니 우선순위? 에러가 나더라. << 을 시프트 연산자로 판단하고 난 에러인 듯 하여, 삼항 연산자에 괄호를 해주니 정상적으로 출력되었다.

정답 코드

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

void input() { cin >> str; }

bool is_idx_P(int idx) { return str[idx] == 'P'; }

bool solve() {
    int p_cnt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (is_idx_P(i))
            p_cnt++;
        else if (p_cnt >= 2 && i + 1 < str.size() && is_idx_P(i + 1)) {
            p_cnt -= 2;
        } else {
            return false;
        }
    }
    if (p_cnt == 1)
        return true;
    else
        return false;
}

void output() { cout << (solve() ? "PPAP" : "NP"); }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    output();
    return 0;
}